Ungleichung von Binomialkoeffi < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Aufgabe 2
b)
Beweise: Für beliebige n, k [mm] \in \IN [/mm] mit k [mm] \le [/mm] 2n gilt:
[mm] \vektor{2n \\ k} \le \vektor{2n \\ n} [/mm] |
Hallo,
ich habe Probleme bei der oben genannten Aufgabe. Ich habe es versucht per Induktion nach n zu beweisen, aber irgendwie kommt am Ende nichts gescheites raus.
Induktionsanfang n = 1 ist klar. Dafür gibt es zwei Möglichkeiten k = 1 und k = 2, da k [mm] \le [/mm] 2n gilt.
Wenn ich jetzt den Induktionsschluss n [mm] \to [/mm] n + 1 machen will erhalte ich am Ende: [mm] \bruch{(2n)! * (2n + 2) * (2n + 1)}{(2n - k)! * k! * (2n - k + 2) * (2n - k + 1)} \le \bruch{(2n)! * (4n + 2)}{n! * n! * (n + 1)}
[/mm]
Da steckt ja die Induktionsvorraussetzung mit drin, aber jetzt muss ich ja noch zeigen, dass [mm] \bruch{(2n + 2) * (2n + 1)}{(2n - k + 2) * (2n - k + 1)} \le \bruch{(4n + 2)}{(n + 1)}. [/mm] Wie mache ich das? Ich komm da irgendwie nicht weiter...
|
|
| |
|
Hallo,
> Beweise: Für beliebige n, k [mm]\in \IN[/mm] mit k [mm]\le[/mm] 2n gilt:
>
> [mm]\vektor{2n \\ k} \le \vektor{2n \\ n}[/mm]
Das kannst du am einfachsten direkt beweisen:
[mm] {2n\choose k}=\frac{(2n)!}{k!(2n-k)!},\qquad {2n\choose n}=\frac{(2n)!}{n!(2n-n)!}
[/mm]
Vergleiche beides miteinander, es wird sich sehr viel wegkürzen.
LG
|
|
|
| |
|
Ja, gut. Das (2n)! kürzt sich weg.
Jetzt habe ich da stehen:
[mm] \bruch{1}{k!*(2n-k)!} \le \bruch{1}{n!*n!}
[/mm]
Kann man pauschal sagen, dass (2n)! > n!*n! ist?
|
|
|
| |
|
> Ja, gut. Das (2n)! kürzt sich weg.
>
> Jetzt habe ich da stehen:
>
> [mm]\bruch{1}{k!*(2n-k)!} \le \bruch{1}{n!*n!}[/mm]
Um das zu zeigen, erweitere erstmal mit dem Hauptnenner. Dann kannst du noch mehr kürzen:
[mm] n!=n(n-1)\cdots(k+1)*k!
[/mm]
Und ...
>
> Kann man pauschal sagen, dass (2n)! > n!*n! ist?
Sicher, wird aber erstmal nicht viel nützen.
LG
|
|
|
| |
|
Hab jetzt mal weiter umgeformt, aber so richtig weiter bringen tut es mich nicht.
[mm] \bruch{1}{k!\cdot{}(2n-k)!} \le \bruch{1}{n!\cdot{}n!} [/mm] | *n!
[mm] \gdw \bruch{n!}{k!\cdot{}(2n-k)!} \le \bruch{1}{n!}
[/mm]
[mm] \gdw \bruch{n*(n-1)*...*(k+1)*k*(k-1)*...*1}{k*(k-1)*...*1\cdot{}(2n-k)!} \le \bruch{1}{n!} [/mm] | Kürzen
[mm] \gdw \bruch{n*(n-1)*...*(k+1)}{(2n-k)!} \le \bruch{1}{n!} [/mm] | *n!
[mm] \gdw \bruch{n*(n-1)*...*(k+1)*n!}{(2n-k)*(2n-k-1)*...*1} \le [/mm] 1 | Lässt sich hier jetzt noch das n! kürzen?
|
|
|
| |
|
> Hab jetzt mal weiter umgeformt, aber so richtig weiter
> bringen tut es mich nicht.
>
> [mm]\bruch{1}{k!\cdot{}(2n-k)!} \le \bruch{1}{n!\cdot{}n!}[/mm] | *n!
>
> [mm]\gdw \bruch{n!}{k!\cdot{}(2n-k)!} \le \bruch{1}{n!}[/mm]
> [mm]\gdw \bruch{n*(n-1)*...*(k+1)*k*(k-1)*...*1}{k*(k-1)*...*1\cdot{}(2n-k)!} \le \bruch{1}{n!}[/mm] | Kürzen
> [mm]\gdw \bruch{n*(n-1)*...*(k+1)}{(2n-k)!} \le \bruch{1}{n!}[/mm] | *n!
> [mm]\gdw \bruch{n*(n-1)*...*(k+1)*n!}{(2n-k)*(2n-k-1)*...*1} \le[/mm] 1 | Lässt sich hier jetzt noch das n! kürzen?
Ja.
Dann zähle mal, wie viel Faktoren jeweils in Zähler und Nenner stehen.
LG
|
|
|
|
