Beweis Fibonacci-Folge < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:19 Mo 24.10.2011 | | Autor: | M4T7 |
| Aufgabe | Exercice 19. Die Fibonacci-Folge [mm] (f_{n}) [/mm] ist rekursiv definiert durch
[mm] f_{n+2}=f_{n+1}+f_{n}
[/mm]
für n= 0, 1, 2, ... mit der Anfangsbedingung [mm] f_{0}=f_{1}=1. [/mm] Zeigen Sie per Induktion, dass für [mm] g=(1+\wurzel{5})/2
[/mm]
[mm] |\bruch{f_{n+1}}{f_{n}} [/mm] - [mm] g|=\bruch{1}{f_{n}g^{n+1}} [/mm] gilt.
Schliessen Sie daraus, dass [mm] \limes_{n\rightarrow\infty} \bruch{f_{n+1}}{f_{n}}=g. [/mm] |
Als Tipp des Assistenten habe ich [mm] x_{n}:=\bruch{f_{n+1}}{f_{n}} [/mm] gewählt. Hab bisher nur geschafft, die Voraussetzung [mm] x_{n}=1+\bruch{1}{x_{n-1}} [/mm] zu finden. Wie ich diese aber im Induktionsschritt verwenden soll, weiss ich nicht. Wie soll ich den Induktionsschritt anfangen bzw. weiterführen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo M4T7,
diese Aufgabe ist ein Klassiker in leicht erneuertem Gewand. Du müsstest selbst hier im Forum allerlei zum Grenzwert der Fibonacci-Folge finden, darunter auch Teilberechnungen wie diese. Probier mal die Suchfunktion.
> Exercice 19. Die Fibonacci-Folge [mm](f_{n})[/mm] ist rekursiv
> definiert durch
>
> [mm]f_{n+2}=f_{n+1}+f_{n}[/mm]
>
> für n= 0, 1, 2, ... mit der Anfangsbedingung
> [mm]f_{0}=f_{1}=1.[/mm] Zeigen Sie per Induktion, dass für
> [mm]g=(1+\wurzel{5})/2[/mm]
>
> [mm]|\bruch{f_{n+1}}{f_{n}}[/mm] - [mm]g|=\bruch{1}{f_{n}g^{n+1}}[/mm] gilt.
>
> Schliessen Sie daraus, dass [mm]\limes_{n\rightarrow\infty} \bruch{f_{n+1}}{f_{n}}=g.[/mm]
>
> Als Tipp des Assistenten habe ich
> [mm]x_{n}:=\bruch{f_{n+1}}{f_{n}}[/mm] gewählt. Hab bisher nur
> geschafft, die Voraussetzung [mm]x_{n}=1+\bruch{1}{x_{n-1}}[/mm] zu
> finden.
Das sieht doch soweit ganz gut aus.
Mach Dir erstmal klar, dass [mm] x_n [/mm] ständig das Vorzeichen wechselt (deswegen ja auch die Betragsstriche in der Aufgabe).
> Wie ich diese aber im Induktionsschritt verwenden
> soll, weiss ich nicht. Wie soll ich den Induktionsschritt
> anfangen bzw. weiterführen?
Fang doch einfach mal an, dann können wir hier doch zusammen drüber schauen. Ich sehe eine Schwierigkeit beim Tipp des Assistenten darin, dass das auf der rechten Seite [mm] f_n [/mm] nicht durch [mm] x_n [/mm] darstellbar ist, vielleicht aber durch [mm] x_n [/mm] und [mm] x_{n-1}. [/mm] Auch das solltest Du versuchen, bevor Du Dich an den Induktionsschritt machst.
Und dann: rechne mal los, so weit Du kommst. Bei den Fibonaccizahlen gibt es ein paar Identitäten, auf die man nicht sofort kommt. Manchmal ist die Lösung viel näher, als man denkt. Das liegt natürlich an der Rekursion mit zwei Vorgängern, wo man doch in der Induktion nur einen Schritt weit geht und [mm] a_{n+1} [/mm] auf [mm] a_n [/mm] zurückführen möchte. Bei Fibonacci schlingert dann immer noch ein [mm] a_{n-1} [/mm] mit in der Gegend herum, das man partout nicht loswerden kann, ohne noch Schlimmeres loszutreten.
Also nur Mut! Wir versuchen gern, Dir dabei zu helfen, den schmalen Weg durch den Dschungel zu schlagen. Es gibt übrigens mehrere - sowohl Wege als auch Dschungel. 
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:17 Di 25.10.2011 | | Autor: | M4T7 |
So, eine Mitstudentin hat mir heute verraten, dass [mm] g=1+\bruch{1}{g} [/mm] der Schlüssel zur Lösung ist. Hier mal mein Lösungsvorschlag:
[mm] |x_{n}-g|=|1+\bruch{1}{x_{n-1}}-1-\bruch{1}{g}|=|\bruch{1}{x_{n-1}}-\bruch{1}{g}|=|\bruch{g-x_{n-1}}{g x_{n-1}}|=\bruch{|g-x_{n-1}|}{g x_{n-1}}=\bruch{|g-x_{n-1}|}{g \bruch{f_{n}}{f_{n-1}}}=...
[/mm]
nach ein paar weiteren Schritten hab ich dann:
[mm] \bruch{|x_{n-2}-g|}{g^2 \bruch{f_{n-1}}{f_{n-2}} \bruch{f_{n}}{f_{n-1}}}
[/mm]
also kürzt sich [mm] f_{n-1} [/mm] weg. Das kann man jetzt n Schritte weitermachen, dann hat man:
[mm] \bruch{|x_{0}-g|}{g^n \bruch{f_{n}}{f_{0}}}=\bruch{|1-g|}{g^n f_{n}}=\bruch{|\bruch{-1}{g}|}{g^n f_{n}}=\bruch{1}{g^{n+1} f_{n}}
[/mm]
So, hoffe das genügt. Wahrscheinlich gibts eine einfachere Methode, doch meine sollte doch auch richtig sein, oder?
Ps: danke für den herzlichen Empfang und die Hilfe, die hier geboten wird. :)
|
|
|
| |
|
Guten Abend!
> So, eine Mitstudentin hat mir heute verraten, dass
> [mm]g=1+\bruch{1}{g}[/mm] der Schlüssel zur Lösung ist.
Oh, das hatte ich als bekannt vorausgesetzt. Es ist eine der beiden Standardgleichungen des goldenen Schnitts. Die andere lautet
[mm] \phi=\bruch{1}{\phi-1}
[/mm]
> Hier mal
> mein Lösungsvorschlag:
>
> [mm]|x_{n}-g|=|1+\bruch{1}{x_{n-1}}-1-\bruch{1}{g}|=|\bruch{1}{x_{n-1}}-\bruch{1}{g}|=|\bruch{g-x_{n-1}}{g x_{n-1}}|=\bruch{|g-x_{n-1}|}{g x_{n-1}}=\bruch{|g-x_{n-1}|}{g \bruch{f_{n}}{f_{n-1}}}=...[/mm]
>
> nach ein paar weiteren Schritten hab ich dann:
>
> [mm]\bruch{|x_{n-2}-g|}{g^2 \bruch{f_{n-1}}{f_{n-2}} \bruch{f_{n}}{f_{n-1}}}[/mm]
>
> also kürzt sich [mm]f_{n-1}[/mm] weg. Das kann man jetzt n Schritte
> weitermachen, dann hat man:
>
> [mm]\bruch{|x_{0}-g|}{g^n \bruch{f_{n}}{f_{0}}}=\bruch{|1-g|}{g^n f_{n}}=\bruch{|\bruch{-1}{g}|}{g^n f_{n}}=\bruch{1}{g^{n+1} f_{n}}[/mm]
>
> So, hoffe das genügt. Wahrscheinlich gibts eine einfachere
> Methode, doch meine sollte doch auch richtig sein, oder?
Ich denke nicht, dass es einfacher geht. Du hast die Aufgabe korrekt gelöst.
> Ps: danke für den herzlichen Empfang und die Hilfe, die
> hier geboten wird. :)
Na, dann sehen wir uns bestimmt wieder.
Bis dahin,
reverend
|
|
|
|
