www.vorkurse.de
Ein Projekt von vorhilfe.de
Die Online-Kurse der Vorhilfe

E-Learning leicht gemacht.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Teams · Forum · Wissen · Kurse · Impressum
Forenbaum
^ Forenbaum
Status Mathe-Vorkurse
  Status Organisatorisches
  Status Schule
    Status Wiederholung Algebra
    Status Einführung Analysis
    Status Einführung Analytisc
    Status VK 21: Mathematik 6.
    Status VK 37: Kurvendiskussionen
    Status VK Abivorbereitungen
  Status Universität
    Status Lerngruppe LinAlg
    Status VK 13 Analysis I FH
    Status Algebra 2006
    Status VK 22: Algebra 2007
    Status GruMiHH 06
    Status VK 58: Algebra 1
    Status VK 59: Lineare Algebra
    Status VK 60: Analysis
    Status Wahrscheinlichkeitst

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Induktionsbeweise" - Beweis Fibonacci-Folge
Beweis Fibonacci-Folge < Induktion < Analysis < Oberstufe < Schule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Induktionsbeweise"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweis Fibonacci-Folge: Aufgabe
Status: (Frage) beantwortet Status 
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.

        
Bezug
Beweis Fibonacci-Folge: Antwort
Status: (Antwort) fertig Status 
Datum: 11:05 Di 25.10.2011
Autor: reverend

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


Bezug
                
Bezug
Beweis Fibonacci-Folge: Idee
Status: (Frage) beantwortet Status 
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. :)

Bezug
                        
Bezug
Beweis Fibonacci-Folge: Antwort
Status: (Antwort) fertig Status 
Datum: 21:39 Di 25.10.2011
Autor: reverend

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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Induktionsbeweise"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorkurse.de
[ Startseite | Mitglieder | Teams | Forum | Wissen | Kurse | Impressum ]