matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenInduktionsbeweiseBeweis Fibonacci-Folge
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
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.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]