Fib. Zahl induktiv beweisen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] f_i [/mm] die i-te Fibonacci-Zahl , also [mm] f_0 [/mm] = 0 , [mm] f_1 [/mm] = 1 und [mm] f_n= f_{n-2} [/mm] + [mm] f_{n-1} [/mm] für n > 1
Beweisen Sie für beliebige n,k [mm] \ge [/mm] 0:
[mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] |
Hallo , um erst mal diese rekursive Formel [mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] zu verstehen:
Sei n = 2 und k = 1.
=>
[mm] f_1 f_2 [/mm] + [mm] f_2 f_3 [/mm] = [mm] f_4
[/mm]
[mm] f_1 [/mm] ist 1 , [mm] f_2 [/mm] ist = [mm] f_0 [/mm] + [mm] f_1 [/mm] , also 1
Also ist [mm] f_1 f_2 [/mm] 1 ( wird nicht addiert ,oder ? )
Dann ist
[mm] f_2 f_3 [/mm] , also [mm] f_2 [/mm] ist [mm] f_0 [/mm] + [mm] f_1 [/mm] , also 1
[mm] f_3 [/mm] ist [mm] f_1 [/mm] + [mm] f_2 (f_2 [/mm] ist 1 , [mm] f_1 [/mm] ist 1 , also ) :
[mm] f_3 [/mm] ist 2
Also habe ich für [mm] f_2 f_3 [/mm] 1 und 2, welche davon nehme ich jetzt ?
[mm] f_4 [/mm] ist [mm] f_2 [/mm] + [mm] f_3 [/mm] , also 3
Würde erstmal diese komische Formel klären wollen..
Vielen Dank im Voraus.
|
|
| |
|
Hallo nochmal,
unabhängig von meiner letzten Frage würde ich gerne trotzdem mit der Induktion weitermachen.
Induktionsanfang: sei n = 0
Dann ist
[mm] f_0 f_0 [/mm] + [mm] f_1 f_1 [/mm] = [mm] f_1
[/mm]
1 = 1 .
Induktionsschritt:
Nehmen an , Aussage [mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] ist richtig für n,k [mm] \in \IN
[/mm]
Zu zeigen ist ; Aussage gilt auch für k+1 , n+1
[mm] f_{k+1} f_{n+1} +f_{k2} [/mm] + [mm] f_{n2} [/mm] = [mm] f_{n+k+3}
[/mm]
Ich würde jetzt den linken Teil der Gleichung , also die Summe , so weit umformen , bis ich auf [mm] f_{n+k+3} [/mm] komme.
Kann ich für [mm] f_{k+1} f_{n+1} [/mm] die Annahme im IS übernehmen ? Oder macht das hier keinen Sinn ?
|
|
|
| |
|
Hallo nochmal,
> unabhängig von meiner letzten Frage würde ich gerne
> trotzdem mit der Induktion weitermachen.
>
> Induktionsanfang: sei n = 0
Hier nimmst Du doch richtig an: n=0, k=0.
> Dann ist
> [mm]f_0 f_0[/mm] + [mm]f_1 f_1[/mm] = [mm]f_1[/mm]
> 1 = 1 .
Ok, erfüllt.
> Induktionsschritt:
> Nehmen an , Aussage [mm]f_k f_n[/mm] + [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm]
> ist richtig für n,k [mm]\in \IN[/mm]
>
> Zu zeigen ist ; Aussage gilt auch für k+1 , n+1
Damit erledigst Du aber nicht alle Fälle, sondern letztlich nur alle, wo n=k ist.
Vom Ansatz her zeigst Du mehr, wenn Du beweist, dass die Aussage dann auch für k+1,n gilt. Da die Formel ja symmetrisch in k,n ist, hast Du damit dann gleichzeitig schon bewiesen, dass die Aussage auch für k,n+1 gilt. Und das reicht, um die komplette doppelte Induktion auf einmal zu erschlagen.
> [mm]f_{k+1} f_{n+1} +f_{k2}[/mm] + [mm]f_{n2}[/mm] = [mm]f_{n+k+3}[/mm]
>
>
> Ich würde jetzt den linken Teil der Gleichung , also die
> Summe , so weit umformen , bis ich auf [mm]f_{n+k+3}[/mm] komme.
Das wird schwierig - und wie gesagt: falscher Ansatz!
> Kann ich für [mm]f_{k+1} f_{n+1}[/mm] die Annahme im IS
> übernehmen ? Oder macht das hier keinen Sinn ?
Das macht nicht nur Sinn, sondern ist im Induktionsbeweis immer nötig. Wenn es nicht nötig wäre, bräuchte man keinen Induktionsbeweis.
Grüße
reverend
|
|
|
| |
|
Hallo , danke für die Antworten.
Ich schreibe es dann gleich nochmal auf und poste es dann hier , aber woran erkennt man , dass die Formel symmetrisch ist ?
|
|
|
| |
|
Hallo,
> Ich schreibe es dann gleich nochmal auf und poste es dann
> hier , aber woran erkennt man , dass die Formel symmetrisch
> ist ?
Vertausch mal n und k. Dann steht immer noch genau die gleiche Formel da.
Grüße
reverend
|
|
|
| |
|
Stimmt , + ist kommutativ.
Okay , also , ich habs jetzt so:
IA:
Sei n=0 und k=0
[mm] f_0 f_0 [/mm] + [mm] f_1 f_1 [/mm] = [mm] f_1
[/mm]
1 = 1 , stimmt.
IS:
Nehmen an , Aussage [mm] f_k f_n [/mm] + [mm] f_{k+1} f_{n+1} [/mm] = [mm] f_{n+k+1} [/mm] ist richtig für n,k [mm] \in \IN
[/mm]
Z.z. : Gilt für k+1 ,n (Stichwort "Symmetrie")
[mm] f_{k+1} f_n [/mm] + [mm] f_{k+2} f_{n+1} [/mm] = [mm] f_{n+k+2}
[/mm]
So ab hier muss ich dann irgendwie umformen, aber ich sehe den Wald vor lauter Bäumen nicht.
Wie kann ich das umformen , bis ich die Annahme einsetzen kann , sodass ich am Ende auf [mm] f_{n+k+2} [/mm] komme.
|
|
|
| |
|
Hallo pc-doctor,
hier kommen wir zum Kern der Aufgabe und damit zum eigentlichen Problem.
Es scheint eine schier unerschöpfliche Fülle von Fibonacci-Aufgaben zu geben. Das ist immer irgendwie mühsam, aber ein paar Sachen haben sie gemeinsam. 
> Stimmt , + ist kommutativ.
Ja, und die Multiplikation auch.
> Okay , also , ich habs jetzt so:
> IA:
> Sei n=0 und k=0
> [mm]f_0 f_0[/mm] + [mm]f_1 f_1[/mm] = [mm]f_1[/mm]
> 1 = 1 , stimmt.
Ist ok, aber Du wirst gleich sehen, dass das nicht reicht.
> IS:
> Nehmen an , Aussage [mm]f_k f_n[/mm] + [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm]
> ist richtig für n,k [mm]\in \IN[/mm]
>
> Z.z. : Gilt für k+1 ,n (Stichwort "Symmetrie")
>
> [mm]f_{k+1} f_n[/mm] + [mm]f_{k+2} f_{n+1}[/mm] = [mm]f_{n+k+2}[/mm]
>
> So ab hier muss ich dann irgendwie umformen, aber ich sehe
> den Wald vor lauter Bäumen nicht.
Hier gibts auch reichlich Bäume.
Wo Du hin willst, ist ... [mm] \text{blabla}=f_{n+k}+f_{n+k+1}=f_{n+k+2}
[/mm]
Das eine ist ja nett, also [mm] f_{n+k+1}. [/mm] Das kommt ja in der Induktionsvoraussetzung vor. Das Problem ist aber [mm] f_{n+k}. [/mm] Damit Du das auch darstellen kannst, wirst Du mehr als Induktionsanfang brauchen. Das ist bei Fibonacci immer so, wenn man Induktion anwenden will.
Das ist ja auch logisch. Sobald Du eine Rekursionsdarstellung von [mm] a_{n+1} [/mm] hast, in der nicht nur [mm] a_n, [/mm] sondern auch [mm] a_{n-1} [/mm] vorkommt, wirst Du einen doppelten Induktionsanfang brauchen. Hier also für n=k=0 und für n=0, k=1 oder umgekehrt (was ja das gleiche ist). Dann kriegst Du auch den Induktionsschritt hin.
Ansonsten braucht man außer dieser (doppelten) IV nur noch die rekursive Definition der Folgenglieder und ein ziemliches Geschick darin, die richtigen Teile der Formel mittels der Rekursion so zu zerlegen, dass man nur bekannte Fibonaccizahlen darin hat.
> Wie kann ich das umformen , bis ich die Annahme einsetzen
> kann , sodass ich am Ende auf [mm]f_{n+k+2}[/mm] komme.
Tja, probiers mal. Es ist ein bisschen "tricky", aber es geht mit den Tipps oben.
Meld Dich mal mit einem Versuch.
Ach ja, der Induktionsschritt geht dann von $n+1$ zu $n+2$, aber das ändert ja nichts.
Grüße
reverend
|
|
|
| |
|
Hallo pc-doctor,
irgendwie machst Du es Dir hier unnötig kompliziert.
> Sei [mm]f_i[/mm] die i-te Fibonacci-Zahl , also [mm]f_0[/mm] = 0 , [mm]f_1[/mm] = 1
> und [mm]f_n= f_{n-2}[/mm] + [mm]f_{n-1}[/mm] für n > 1
> Beweisen Sie für beliebige n,k [mm]\ge[/mm] 0:
>
> [mm]f_k f_n[/mm] + [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm]
>
> Hallo , um erst mal diese rekursive Formel [mm]f_k f_n[/mm] +
> [mm]f_{k+1} f_{n+1}[/mm] = [mm]f_{n+k+1}[/mm] zu verstehen:
Die ist nicht rekursiv. Rekursiv ist hier nur das Bildungsgesetz der Fibonaccifolge; genau darum verwendest Du ja später auch vollständige Induktion.
> Sei n = 2 und k = 1.
>
> =>
> [mm]f_1 f_2[/mm] + [mm]f_2 f_3[/mm] = [mm]f_4[/mm]
>
> [mm]f_1[/mm] ist 1 , [mm]f_2[/mm] ist = [mm]f_0[/mm] + [mm]f_1[/mm] , also 1
> Also ist [mm]f_1 f_2[/mm] 1 ( wird nicht addiert ,oder ? )
Nein, da wird nichts mehr addiert, es ist doch eine ganz normale Multiplikation.
> Dann ist
>
> [mm]f_2 f_3[/mm] , also [mm]f_2[/mm] ist [mm]f_0[/mm] + [mm]f_1[/mm] , also 1
> [mm]f_3[/mm] ist [mm]f_1[/mm] + [mm]f_2 (f_2[/mm] ist 1 , [mm]f_1[/mm] ist 1 , also ) :
> [mm]f_3[/mm] ist 2
> Also habe ich für [mm]f_2 f_3[/mm] 1 und 2, welche davon nehme ich
> jetzt ?
Beide. Aus [mm] f_2=1 [/mm] und [mm] f_3=2 [/mm] folgt [mm] f_2f_3=1*2=2.
[/mm]
> [mm]f_4[/mm] ist [mm]f_2[/mm] + [mm]f_3[/mm] , also 3
>
> Würde erstmal diese komische Formel klären wollen..
Du hast das schon richtig verstanden.
Einfacher für dieses Beispiel: [mm] f_0=0, f_1=1, f_2=1, f_3=2, f_4=3
[/mm]
Dann einsetzen: [mm] f_1f_2+f_2f_3=1*1+1*2=3=f_4. [/mm] Fertig.
> Vielen Dank im Voraus.
Damit hast Du ja aber nur ein Beispiel geklärt.
Zeigen sollst Du, dass das für beliebige n,k gilt, also z.B. auch für [mm] f_{126}f_{439}+f_{127}f_{440}=f_{566}.
[/mm]
Grüße
reverend
|
|
|
|
