Induktionsvermutung von k(k+m-1)?
Hatte jetzt schon viele Ansätze, scheine aber etwas total offensichtliches zu übersehen...
1 Antwort
Hallo,
es ist doch offensichtlich, daß die Summe (k=1-k=n) über k*(k+1)*...*(k+m-1)
[n*(n+1)*...*(n+m)]/(m+1) ist, denn in der Summenformel taucht im Zähler das Folgeglied von (k+m-1) als letzter Faktor auf, während im Nenner m+1 erscheint.
Ist m=3, geht die Summe bis k+2, während die Summenformel bis n+3 geht und im Nenner eine 4 steht.
Wie gehst Du nun beim Induktionsbeweis vor?
Du beweist zunächst, daß die Formel für n=1 stimmt, wenn die Summe also nur von k=1 bis k=1 läuft:
1*2*...*(1+m-1), also 1*2*...*m=(1*2*...*m*(m+1))/(m+1) ist.
Wenn Du den Zähler gegen den Nenner kürzt, bleibt 1*2*...*m, also genau der Term, der hinter dem Summenzeichen steht. Damit ist der Induktionsanfang für n=1 gezeigt.
Zu zeigen ist nun, daß die Summenformel auch für n+1 stimmt, denn dann stimmt sie für jeden Nachfolger von n. Für n=1 ist die Formel bereits bewiesen; gilt sie auch für den Nachfolger vom jeweiligen n, muß sie dann auch für n=2, n=3 usw. gelten.
Die Schwierigkeit dabei ist nun zu überlegen, was sich denn ändert, wenn Du die Summe über k=1 bis k=n zu k=1 bis k=n+1 veränderst.
Nimm an, Du läßt k von 1 bis 3 laufen und wählst auch m=3.
Dann bekommst Du die Summe 1*2*3+2*3*4+3*4*5, denn bei m=3 hast Du die Faktoren k, (k+1) und (k+2), denn m-1=2, Du hast also eine Summe aus Produkten von je drei Faktoren, die aus drei aufeinanderfolgenden Zahlen bestehen.
Nimmst Du n=4, kommt als letzter Summand 4*5*6 dazu, also (n+1)*(n+2)*(n+3).
Wenn wir m nicht festlegen, besteht der letzte Summand aus m Faktoren, die mit (n+1) beginnen und bei n+m aufhören.
Zur bisherigen Summe kommt also der Summand (n+1)*(n+2)*...*(n+m) dazu.
Bei der vollständigen Induktion darfst Du mit der Behauptung arbeiten.
Du benutzt also die Summenformel für die Summe, die für k=1 bis k=n gilt, addierst den nächsten Summanden und beweist, daß die neue Summe das Gleiche ist, als würdest Du sofort n+1 statt n in die Summenformel eingeben.
Du mußt also zeigen, daß [n*(n+1)*...*(n+m)]/(m+1)+(n+1)*...*(n+m) das Gleiche ist wie [(n+1)*(n+2)*...*(n+m)*(n+m+1)]/(m+1) ist.
Der Trick ist hier, daß Du mit Fakultäten arbeitest.
n*(n+1)*...*(n+m)=(n+m)!/(n-1)! usw.
Wandle also in Fakultäten um, mach alle Brüche gleichnamig und vergleiche anschließend die Zähler, dann sollte Dir das Kunststück gelingen.
Zur Information: Ich selbst habe es geschafft, mich dabei aber mindestens fünfmal verrechnet. Du brauchst ein wenig Geduld, dann wird es am Ende klappen.
Herzliche Grüße,
Willy
Ahhh habe ich mich gerade geärgert. Ich hatte diese Idee ganz am Anfang, hatte es aber nicht kombiniert, dass im Zähler noch das Folgeglied als letzter Faktor auftaucht. Dumm. Danke vielmals..!!
n*(n+1)*...*(n+m)=(n+m)!/(n-1)! usw. dieser Schritt ist mir unklar. Wo kommt das im Nenner her?
Achja. Man Fakultäten sind auch so lang her. Logisch. Kann dir nicht genug danken. :D
Hatte mIr nochmal Fakultäten angeschaut. Doch ich merke immer wieder, wie ich in der Praxis darüber stolper. Bin aber (wenn auch mit riesiger Hilfe deinerseits) drauf gekommen. Das braucht noch um einiges mehr Übung!
Noch ein Tipp: Gemeinsamer Nenner ist n!*(m+1).
In einem der Brüche taucht der Nenner (n-1)!*(m+1) auf.
Wenn Du aber im Zähler den zusätzlichen Faktor n unterbringst, kannst Du (n-1)! im Nenner zu n! umwandeln. Das war bei mir der entscheidende Punkt, um die Sache sauber ins Ziel zu bringen.
Ich setze voraus, daß Du mit Fakultäten vertraut bist. Falls nicht, solltest Du Dich darum zuerst kümmern, ansonsten wirst Du bei diesem Beweis Probleme bekommen.