Konvergenz und Fibonacci-Folge
Nicolas v. Wedel
bei der Suche nach einem griffigen Beweis dafï¿œr, dass der Grenzwert der
Fibonacci-Folge Phi (Streckenverhï¿œltnis des Goldnen Schnitt) ist, stolperte
ich ueber Vorgehensweisen, die entweder falsch sind oder aber - ich habe was
nicht verstanden:
1. Bestimmung des ANGENOMMENEN Grenzwertes (... geht relativ fix und man ist
bei Phi angekommen)
2. Bestimmung der Konvergenz der Fibonacci-Folge durch
a) Nachweis der Beschrï¿œnktheit
b) Nachweis der Monotonie
Soweit alles klar. Wo ich nicht mitkomme ist, daￜ einige (bspw. Harald Scheid
in seinen "Folgen und Funktionen") die Beschrï¿œnktheit der Folge aus dem 1.
Beweisteil nehmen, also (1<=Glied der Folge <= Phi) und nur noch die
Monotonie nachweisen. Das aber ist doch logisch nicht zulï¿œssig!? Denn die
Beschrï¿œnktheit beruht ja nur auf der ANNAHME, es gï¿œbe einen Grenzwert der
Folge.
Sehe ich das richtig oder falsch?
Dank fï¿œr kurze Info.
Gruss Nico
Wolfgang Kirschenhofer
> Hallo zusammen,
>
> bei der Suche nach einem griffigen Beweis dafür, dass der Grenzwert der
> Fibonacci-Folge Phi (Streckenverhältnis des Goldnen Schnitt) ist, stolperte
> nicht verstanden:
>
> 1. Bestimmung des ANGENOMMENEN Grenzwertes (... geht relativ fix und man ist
> bei Phi angekommen)
>
> 2. Bestimmung der Konvergenz der Fibonacci-Folge durch
> b) Nachweis der Monotonie
>
> Soweit alles klar. Wo ich nicht mitkomme ist, daß einige (bspw. Harald Scheid
> in seinen "Folgen und Funktionen") die Beschränktheit der Folge aus dem 1.
> Beschränktheit beruht ja nur auf der ANNAHME, es gäbe einen Grenzwert der
> Sehe ich das richtig oder falsch?
>
>
> Gruss Nico
>
Hallo Nico!
Die Fibonacci-Folge ist unbeschränkt nach oben.
Vermutlich meinst die die Folge <x_n> der Fibonacci-Quotienten
x_n:= F_{n+1}/F_n. Diese Folge ist aber nicht monoton; sie konvergiert
gegen die Schnittzahl Phi.
Der einfachste Konvergenzbeweis geht mit Hilfe der Binet'schen Formel:
Es gilt F_n = (1/sqrt(5))*(a^n - b^n), wobei a:=(1+sqrt(5))/2 und
b:=(1-sqrt(5))/2 ist.
Es gilt daher x_n = (a^(n+1)- a^(n+1)/(a^n - b^n)=
= a* (1- (b/a)^(n+1))/(1 - (b/a)^n). (*)
Nun ist aber abs(b/a)= (3-sqrt(5))/2 < 1 .
Aus (*) folgt daher lim(n->oo) x_n = a = Phi.
Die Binet'sche Formel erhält man durch Lösung der Differenzengleichung
F_{n+2}=F_{n+1} + F_n mit F_1=F_2=1 .
Gruss,
Wolfgang Kirschenhofer
Wolfgang Kirschenhofer
> Hallo zusammen,
>
> bei der Suche nach einem griffigen Beweis dafür, dass der Grenzwert der
> Fibonacci-Folge Phi (Streckenverhältnis des Goldnen Schnitt) ist, stolperte
> nicht verstanden:
>
> 1. Bestimmung des ANGENOMMENEN Grenzwertes (... geht relativ fix und man ist
> bei Phi angekommen)
>
> 2. Bestimmung der Konvergenz der Fibonacci-Folge durch
> b) Nachweis der Monotonie
>
> Soweit alles klar. Wo ich nicht mitkomme ist, daß einige (bspw. Harald Scheid
> in seinen "Folgen und Funktionen") die Beschränktheit der Folge aus dem 1.
> Beschränktheit beruht ja nur auf der ANNAHME, es gäbe einen Grenzwert der
> Sehe ich das richtig oder falsch?
>
>
> Gruss Nico
>
Hallo Nico!
Korrektur eines Schreibfehlers:
Es muß natürlich heißen:
Es gilt daher x_n = (a^(n+1)- b^(n+1))/(a^n - b^n)
Wolfgang Kirschenhofer
Thomas Nordhaus
>
> Die Fibonacci-Folge ist unbeschr�nkt nach oben.
> Vermutlich meinst die die Folge <x_n> der Fibonacci-Quotienten
> x_n:= F_{n+1}/F_n. Diese Folge ist aber nicht monoton; sie konvergiert
> gegen die Schnittzahl Phi.
> Der einfachste Konvergenzbeweis geht mit Hilfe der Binet'schen Formel:
Hier noch ein alternativer Beweis (der nur allgemeine, elementare
Kenntnisse von 1-dimensionalen Differenzengleichungen bzw.
1-dimensionalen diskreten dynamischen Systemen benutzt):
Die x_n erf�llen die Rekursionsgleichung x_(n+1) = f(x_n) mit f(x) = 1 +
1/x. X = (sqrt(5)+1)/2 = 1,618... ist der einzige positive Fixpunkt von
f. Da |f'(X)| = 1/X^2 < 1 konvergiert die Folge der x_n zun�chst lokal,
d.h. f�r Anfangswerte x0 in der N�he von X. Die Konvergenz ist
allerdings nicht monoton sondern "alternierend um X herum".
Die globale Konvergenz (f�r positive Startwerte) bekommt man, wenn man
sich g(x) := f(f(x)) anschaut. g(x) = 2 - 1/(x+1) ist monoton steigend
mit g'(X) = 1/(X+1)^2 (= (f'(X))^2). Also 0 < g'(X) < 1. Die Folge x0,
g(x0), g(g(x0)) ... konvergiert dann aber monoton steigend f�r x0 < X
bzw. monoton fallend f�r x0 > X gegen X. Dann muss aber auch die Folge
der Iterierten unter f gegen X konvergieren - sie setzt sich n�mlich
durch "Verschr�nkung" von 2 gegen X konvergierender Folgen von
Iterierten unter g zusammen.
--
Thomas Nordhaus
k. Schubser
> Die Binet'sche Formel erh�lt man durch L�sung der Differenzengleichung
>
> F_{n+2}=F_{n+1} + F_n mit F_1=F_2=1 .
Siehe:
http://delphi.zsg-rottenburg.de/rekursivefolgen.html
Gru�
K.
k. Schubser
> Die Binet'sche Formel erh�lt man durch L�sung der Differenzengleichung
>
> F_{n+2}=F_{n+1} + F_n mit F_1=F_2=1 .
Dabei handelt es sich um eine
homogene lineare rekursive Folge 2. Grades ...,
deren Glieder man durch eine geschlossene Formel angeben
kann. Siehe:
http://delphi.zsg-rottenburg.de/rekursivefolgen.html
Gru�
K.
Nicolas v. Wedel
(in article <0001HW.C740AE5F...@us1.usenet-server.de>):
Dank Euch, vor allem Wolfgang fuer den Binet-Exkurs. Sorry - natuerlich
meinte ich die Folge der Fibonacci-Quotienten :-)
Mein Gedanke war ehedem, den Konvergenznachweis eben OHNE die (anmutige)
Binet-Formel zu erbringen, also wie oben angefï¿œhrt.
Streng genommen fehlte mir ja nur noch der Nachweis der Beschrï¿œnktheit, wenn
ich - und das ist mein Problem - Phi nicht als obere Schranke heranziehe, die
ich als gewonnenen Grenzwert ja lediglich ANGENOMMEN habe.
Andersrum gefragt:
Habe ich die Konvergenz der Fibonacci-Quotientenfolge logisch richtig
gezeigt, wenn ich
1. den Grenzwert bestimme ï¿œber die Annahme, die Folge habe einen Grenzwert
(also Phi erhalte)
2. mit eben diesem Grenzwert die Beschrï¿œnktheit der Folge zeige und
3. die Monotonie nachweise
gemￜￜ dem Sprￜchlein "monoton und beschrￜnkt ist konvergent".
Grï¿œsse
Nico
Jutta Gut
"Nicolas v. Wedel" <4...@wirklichkeiten.com> schrieb
>
> Habe ich die Konvergenz der Fibonacci-Quotientenfolge logisch richtig
> gezeigt, wenn ich
>
> 1. den Grenzwert bestimme ï¿œber die Annahme, die Folge habe einen Grenzwert
> (also Phi erhalte)
> 2. mit eben diesem Grenzwert die Beschrï¿œnktheit der Folge zeige und
> 3. die Monotonie nachweise
>
> gemￜￜ dem Sprￜchlein "monoton und beschrￜnkt ist konvergent".
Wie schon ein paarmal erwï¿œhnt, ist die Folge der Fibonacci-Quotienten eben
nicht monoton: 1/1 < 2/1, 2/1 > 3/2, 3/2 < 5/3 ... Das Kriterium "monoton
und beschrï¿œnkt ist konvergent" nï¿œtzt dir also bei diesem Beispiel nichts. Du
kï¿œnntest vielelicht zeigen, dass die Folge alternierend ist (also
abwechselnd steigend und fallend) und |a_n+1 - a_n| gegen 0 geht.
Grￜￜe
Jutta
Hendrik van Hees
Fibonaccifolgen einen zweidimensionalen Untervektorraum des Vektorraums
der Folgen bilden und daￜ es zwei linear unabhￜngige geometrische Folgen
gibt, die man als Basis verwenden kann. Dann wird der Beweis fï¿œr den
Grenzwert der Quotienten (Goldener Schnitt) schï¿œn einfach :-).
Jutta Gut wrote:
--
Hendrik van Hees
Institut fï¿œr Theoretische Physik
Justus-Liebig-Universitï¿œt Gieï¿œen
http://theorie.physik.uni-giessen.de/~hees/
Wolfgang Kirschenhofer
> Ich weiß nicht, ob schon jemand den Tip gegeben hat, daß die
> gibt, die man als Basis verwenden kann. Dann wird der Beweis für den
> Grenzwert der Quotienten (Goldener Schnitt) schön einfach :-).
>
Hallo Hendrik!
Siehe meinen Beweis vom 6.12.09
Gruß,
Wolfgang Kirschenhofer
Wolfgang Kirschenhofer
>
> "Nicolas v. Wedel" <4...@wirklichkeiten.com> schrieb
>
>>
>> Habe ich die Konvergenz der Fibonacci-Quotientenfolge logisch richtig
>> gezeigt, wenn ich
>>
>> Grenzwert
>> (also Phi erhalte)
>> 2. mit eben diesem Grenzwert die Beschränktheit der Folge zeige und
>> 3. die Monotonie nachweise
>>
>> gemäß dem Sprüchlein "monoton und beschränkt ist konvergent".
>
> Wie schon ein paarmal erwähnt, ist die Folge der Fibonacci-Quotienten
> Beispiel nichts. Du könntest vielelicht zeigen, dass die Folge
> a_n| gegen 0 geht.
>
> Jutta
Hallo Nicolas!
Sei wieder x_n:= F_{n+1}/F_n , n>=1.
Nun ein Beweis,daß lim(n->oo) x_n = Phi, ohne die Binet'sche Formel zu
verwenden:
Ich verwende:
x_n >=1 (1)
und
Phi - 1 = 1/Phi (2)
Aus F_{n+1}=F_n + F_{n-1} folgt
x_n = 1 + 1/x_{n-1} (3)
Aus (3) und (2) folgt
Phi - x_n = Phi -1 - 1/x_{n-1}= 1/Phi - 1/x_{n-1} =
=(x_{n-1} - Phi)/(Phi*x_{n-1}) und daraus weiter
|Phi-x_n| = |Phi-x_{n-1}|/(Phi*x_{n-1}) und daraus folgt weiter,
wegen x_n>=1, daß
|Phi-x_n| <= |Phi-x_{n-1}|/Phi (4)
Und aus (4) folgt durch Induktion, daß
|Phi-x_n| <= |Phi-x_1|/(Phi^(n-1)) (5)
Wegen Phi=(1+sqrt(5))/2 > 1, folgt aus (5),daß
|Phi - x_n| -> 0 für n->oo
Grüße,
Wolfgang Kirschenhofer