Abschätzung Binomialkoeffizient

Neue Frage »

11.11.2015, 07:59	columkle1892	Auf diesen Beitrag antworten »
Abschätzung Binomialkoeffizient Ich stehe vor der Lösung folgender Aufgabe: Es seien $\begin{eqnarray} n \end{eqnarray}$ und $\begin{eqnarray} k \end{eqnarray}$ natürliche Zahlen mit $\begin{eqnarray} n\geq k\geq 1 \end{eqnarray}$ . Man beweise, dass $\begin{eqnarray} \binom{n}{k}\geq \Big(\frac{n}{k}\Big)^k \end{eqnarray}$ Ich habe bislang folgendes versucht: $\begin{eqnarray} \binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{k!}\geq \frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{k^k} \end{eqnarray}$ Weiter komme ich nicht
11.11.2015, 09:06	Elvis	Auf diesen Beitrag antworten »
Der letzte Schritt führt offenbar nicht zum Ziel, weil der Zähler nicht größer oder gleich $\begin{eqnarray} n^k \end{eqnarray}$ ist. Gehe einen Schritt zurück und schreibe die Fakutät im Nenner als Produkt absteigender Faktoren.
11.11.2015, 09:14	columkle1892	Auf diesen Beitrag antworten »
Also: $\begin{eqnarray} \binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{k\cdot(k-1)\cdot\ldots\cdot 1} \end{eqnarray}$ Ich sehe leider nicht wie mir das weiterhelfen kann.
11.11.2015, 11:00	Elvis	Auf diesen Beitrag antworten »
Ich sehe leider nicht, wie Dein Ansatz weiterhelfen kann. Der 1. Faktor $\begin{eqnarray} \frac n k \end{eqnarray}$ ist schon mal $\begin{eqnarray} \ge \frac n k \end{eqnarray}$ . Wenn das auch für die anderen Faktoren gilt, bist Du fertig. Wenn nicht, musst Du nachdenken.
11.11.2015, 11:29	HAL 9000	Auf diesen Beitrag antworten »
Vielleicht ist columkle1892 gar nicht klar, was du mit 1.Faktor (bzw. nachfolgenden Faktoren) in dem Zusammenhang überhaupt meinst. Daher bringe ich mal die diesbezüglich klärende Darstellung $\begin{align} \binom{n}{k} = \frac{n}{k} \cdot \frac{n-1}{k-1} \cdot \ldots \cdot \frac{n-k+2}{2} \cdot \frac{n-k+1}{1} \end{align}$ an - es ist ja sicher diese Gruppierung der Terme, die du meinst.
11.11.2015, 11:47	columkle1892	Auf diesen Beitrag antworten »
Danke für die bisherige Hilfe. Nun muss ja nur noch die folgende Ungleichung gezeigt werden: $\begin{eqnarray} \frac{n}{k}\cdot\frac{n-1}{k-1}\cdot\ldots\cdot\frac{n-k+2}{2}\cdot\frac{n-k+1}{1}\geq \frac{n}{k}\cdot\frac{n}{k}\cdot\ldots\cdot\frac{n}{k}\cdot\frac{n}{k} \end{eqnarray}$ Wie stelle ich das an?
Anzeige

11.11.2015, 12:00	columkle1892	Auf diesen Beitrag antworten »
Anders formuliert $\begin{eqnarray} \prod_{i=0}^{k-1}\frac{n-i}{k-i}\geq \Big(\frac{n}{k}\big)^k \end{eqnarray}$
11.11.2015, 12:12	Elvis	Auf diesen Beitrag antworten »
Ja. Zeige es doch einfach für den 2. Faktor, und überlege, warum es dann auch für den 3. und 4. und 5. (jetzt wird mir langweilig) gilt.
11.11.2015, 12:28	columkle1892	Auf diesen Beitrag antworten »
Ich habe jetzt folgendes: $\begin{eqnarray} \binom{n}{k}=\frac{n!}{k!(n-k)!}=\frac{n\cdot(n-1)\cdot\ldots\cdot(n-k+1)}{k\cdot(k-1)\cdot\ldots\cdot 1}=\frac{n}{k}\cdot\frac{n-1}{k-1}\cdot\ldots\cdot\frac{n-k+2}{2}\cdot\frac{n-k+1}{1}=\prod_{i=0}^{k-1}\frac{n-i}{k-i}=\prod_{i=1}^{k}\frac{n-i+1}{k-i+1}\geq\prod_{i=1}^{k}\frac{n}{k}=\Big(\frac{n}{k}\Big)^k \end{eqnarray}$ Kann man das so stehen lassen?
11.11.2015, 12:47	Elvis	Auf diesen Beitrag antworten »
Ja, das kann man so stehen lassen, aber das ist kein Beweis. Du musst beweisen: $\begin{eqnarray} \frac {n-1}{k-1}\ge \frac n k \end{eqnarray}$
12.11.2015, 09:00	columkle1892	Auf diesen Beitrag antworten »
Umgeformt ergibt sich ja: $\begin{eqnarray} nk-k\geq nk-n \end{eqnarray}$ bzw. $\begin{eqnarray} 1\leq k\leq n \end{eqnarray}$ Da nach Voraussetzung $\begin{eqnarray} k\leq n \end{eqnarray}$ gilt ist dies stets erfüllt Die Gültigkeit der Produktungleichung folgt aus den Anordnungsaxoimen. Reicht das als Beweis?
12.11.2015, 09:19	Elvis	Auf diesen Beitrag antworten »
Jetzt wissen wir, dass $\begin{eqnarray} \frac n k\ge\frac n k \end{eqnarray}$ und $\begin{eqnarray} \frac {n-1}{k-1}\ge \frac n k \end{eqnarray}$ gilt. Was ist dann mit den anderen Faktoren $\begin{eqnarray} \frac {n-2}{k-2} = \frac {(n-1)-1} {(k-1)-1}, \frac {n-3}{k-3} = \frac {(n-2)-1} {(k-2)-1}, ... \end{eqnarray}$ ?

Neue Frage »

Antworten »

Abschätzung Binomialkoeffizient

Verwandte Themen