induktion
Von: , Frage gestellt am Do, 22. Apr 2004
Hallo, an alle zusammen..hätte da mal eine Frage, wer mir bei folgender aufgabe weiterhelfen kann......
Summe k=0 bis n (n über k)² = (2n über n) für alle n Elem N
das is zu zeigen..??
3 Antworten zu dieser Frage
-
Antwort von nach 5 Stunden 0 hilfreich
Re: induktion
Hallo Nadine!
Keine Lösung, aber ein paar Denkanstöße:
Induktion ist schonmal der richtige Ansatz.
Du musst also erstmal einen Punkt (in dem Fall ein n) suchen, wo Du die Induktion verankern kannst. Sinnvoller weise liegt der am Rand des Definitionsbereiches. Unendlich ist etwas unhandlich, also nehmen wir welches n?
Die Formel, die sich dafür ergibt, ist nicht soo schwierig. Sie lautet?
Gilt der Satz für diese n?
Was geschieht nun, wenn Du n um eins erhöhst? Setze dabei voraus, dass der Satz für alle kleineren Zahlen schon bewiesen ist.
Kommst Du jetzt weiter?
Gruß
Arndt [Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
-
Antwort von nach einem Tag 1 hilfreich
Re: induktion
Hallo,
zuächst - kombinatorisch sieht man diese Gleichheit sehr leicht ein. (2n über n) ist die Anzahl der Möglichkeiten, z.B. n Kugeln in 2n Löcher zu plazieren (mit max. einer Kugel pro Loch). Teilt man die 2n Löcher in zwei Hälften wird schnell klar, daß
Σ0<=k<=n (n über k)2=Σ0<=k<=n (n über k)(n über n-k)
unter dieser Betrachtung ebenfalls die Anzahl der Möglichkeiten n Kugeln in 2n Löcher zu plazieren beschreibt (resp. k Kugeln in die erste Hälfte, n-k Kugeln in die zweite Hälfte).
Zum Induktionsbeweis. Z.Z. ist:
A1(n)=Σ0<=k<=n (n über k)2 = (2n über n) für alle n∈IN
dazu beweisen wir "parallel" die Behauptung:
A2(n)=Σ0<=k<=n-1 (n über k)(n über k+1)=(2n über n-1) für n>=1
Induktionanfang:
A1(0): (0 über 0)=1=(2*0 über 0)
A1(1): (1 über 0)+(1 über 1)=2=(2*1 über 1)
A2(1): (1 über 0)*(1 über 1)=1=(2*1 über 0)
Induktionsschritt: n -> n+1 (n>=1)
Es gelte A1(n) und A2(n). Z.Z. ist A1(n+1) und A2(n+1).
Dazu verwenden wir:
(1) (n über k) + (n über k+1)=(n+1 über k+1)
(2) 2*(2n+1 über n)=(2(n+1) über n+1)
Anm: Das folgt leicht aus (1), da
2*(2n+1 über n)=(2n+1 über n)+(2n+1 über n)=(2n+1 über n)+(2n+1 über n+1)=(2(n+1) über n+1)
Es gilt:
Σ0<=k<=n+1 (n+1 über k)2 =
1 + Σ0<=k<=n (n+1 über k+1)2=
2 + Σ0<=k<=n-1 ((n über k) + (n über k+1))2=
2 + Σ0<=k<=n-1 (n über k)2 + 2*(n über k)(n über k+1)+(n über k+1)2=
2*[(2n über n) + Σ0<=k<=n-1 (n über k)(n über k+1)]=
2*[(2n über n) + (2n über n-1)]=2*(2n+1 über n)=(2(n+1) über n+1)
d.h. es folgt A1(n+1). A2(n+1) überlaß ich Dir.
Gruss
Enno