Fibonacci Zahlen

,,Die Konstruktion beider Körper (Dodekaeder Und Ikosaeder), vor allem aber die des Fünfecks selbst, ist nicht durchführbar ohne jene Proportion, die die heutigen Mathematiker die göttliche nennen. Diese ist aber so beschaffen, daß die beiden kleineren Glieder einer stetigen Proportion zusammen das dritte ergeben, und in dieser Weise bildet immer die Summe zweier benachbarter Glieder das unmittelbar folgende, wobei die gleiche Proportion bis ins Unbegrenzte fortgeht. In Zahlen das Ergebnis vollkommen auszudrücken ist unmöglich. Je weiter wir uns jedoch von der Einheit entfernen, desto besser wird die Annäherung. Es seien die beiden kleinsten Zahlen 1, und 1 , die Du Dir als ungleichwertig vorstellen musst. Addiert ergeben sie 2. Die größere hinzu addiert ergibt 3 ...

Nach Analogie dieser sich fortsetzenden Proportion ist, wie ich glaube, das Zeugungsvermögen versinnbildlicht, und so wird in der Blüte dem Zeugungsvermögen ein unverfälschtes fünfzackiges Fähnlein vorangetragen.`` [KepII, Seite 18]

Betrachten wir aufs Neue die am Fünfeck rekursiv (oder besser fortgreifend je nach dem wie man es anschaut) definierte Folge.

an : = an+1 + an+2 (5)

Es entsteht eine Folge von Zahlen, die ins unendlich kleine fortfährt. Man kann sich vorstellen, sie kommt aus dem unendlich Großen. Ein Fünfeck, welches sich zusammenzieht kollabiert. Oder wir fassen es als ein Fünfeck auf welches explodiert aus dem Urknall entsteht. In jedem Fall sucht man nach Anfang und Ende und findet nichts. Es ist ein schönes Beispiel für die These eines Kollegen von mir Herrn Agerer. Er ist Hobbyastronom. Vielleicht schauen wir, wenn wir ins Universum blicken in den Mikrokosmos und umgekehrt. Möglicherweise schließt die Unendlichkeit das Gigantische mit dem winzigen in einem Kreis zusammen. Eine Vorstellung, die nur auf den ersten Blick hin absurd ist. Auf jeden Fall ist es auch in unserm Fall künstlich der Folge einen Anfang oder ein Ende zu geben.

Definition 2.1   Ist f : $ \mbox{$\mathbb Z$}$ $ \rightarrow$ V eine Funktion, wobei V ein Vektorraum ist, so heißt f eine $ \mbox{$\mathbb Z$}$ Folge. Die Folge heißt golden, wenn für alle z $ \in$ $ \mbox{$\mathbb Z$}$ gilt: f (z) = f (z + 1) + f (z + 2). Sie heißt Fibonacci Folge, wenn f (z + 2) = f (z + 1) + f (z) für alle z $ \in$ $ \mbox{$\mathbb Z$}$ gilt. Ist f (0) = 0 und f (1) = 1 und f (z + 2) = f (z + 1) + f (z) so spricht man von der Fibonacci Folge schlechthin

Satz 2.1   Die Menge der Fibonacci Folgen bilden einen zweidimensionalen Unterraum der Folgen.

Beweis:Sind f, g $ \in$ Fib, so gilt (f + g)(z + 2) = f (z + 2) + g(z + 2) = (f + g)(z + 1) + (f + g)(z). Die Fibonaccifolge selber ist in Fib. Außerdem ist g(z) : = f (z + 1) sicher eine Fibonacci Folge. Behauptung: Ist h eine Folge in Fib, so gibt es $ \alpha$,$ \beta$ $ \in$ $ \mbox{$\mathbb{R}$}$ mit h = f$ \alpha$ + g$ \beta$

Wir wählen $ \beta$ = h(0) und $ \alpha$ = h(1) - h(0) und behaupten h(z) = f (z) . $ \alpha$ + g(z) . $ \beta$ für alle z $ \in$ $ \mbox{$\mathbb Z$}$. Für z = 0, z = 1 ist dies sicher richtig. Gelte die Behauptung für z. Dann folgt h(z + 1) = h(z) + h(z - 1) = f (z) . $ \alpha$ + f (z - 1) . $ \alpha$ + (g(z) + g(z - 1)) . $ \beta$ = f (z + 1) . $ \alpha$ + g(z + 1) . $ \alpha$. Damit folgt die Behauptung für alle positiven z $ \in$ $ \mbox{$\mathbb Z$}$. Für die negativen z ist die Behauptung genauso einfach. $ \Box$

Betrachten wir auf neue die goldene Folge (az| z $ \in$ $ \mbox{$\mathbb Z$}$). Schreibt man sie als Zuordnung zwischen Zahlenpaaren, so sieht das folgendermaßen aus:

$\displaystyle \left(\vphantom{\begin{array}{c} a_{z+1}\\  a_{z+2}\\  \end{array}}\right.$$\displaystyle \begin{array}{c} a_{z+1}\\  a_{z+2}\\  \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} a_{z+1}\\  a_{z+2}\\  \end{array}}\right)$ $\displaystyle \mapsto$ $\displaystyle \left(\vphantom{\begin{array}{c} a_{z}\\  a_{z+1}\\  \end{array}}\right.$$\displaystyle \begin{array}{c} a_{z}\\  a_{z+1}\\  \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} a_{z}\\  a_{z+1}\\  \end{array}}\right)$ = $\displaystyle \left(\vphantom{\begin{array}{c} a_{z+1}+a_{z+2}\\  a_{z+1}\\  \end{array}}\right.$$\displaystyle \begin{array}{c} a_{z+1}+a_{z+2}\\  a_{z+1}\\  \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} a_{z+1}+a_{z+2}\\  a_{z+1}\\  \end{array}}\right)$ (6)

Hinweise:

  1. Die Gleichung 6 ist ein Spezialfall einer so genannten linearen Rekursionsgleichung: Xn+2 : = a . xn+1 + b . xn mit a, b $ \in$ $ \mbox{$\mathbb{R}$}$. Die Lösungen solcher Rekursionsgleichungen bilden stets einen zweidimensionalen Vektorraum. Der Beweis überträgt sich unschwer auf die allgemeine Situation.

Die Gleichung 6 definiert einen Homomorphismus f : $ \mbox{$\mathbb{R}$}$2 $ \rightarrow$ $ \mbox{$\mathbb{R}$}$2. Die zugehörige Matrix ist

F = $\displaystyle \begin{pmatrix}1 & 1\\  1 & 0 \end{pmatrix}$ (7)

Satz 2.2   Sei F = $ \begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}$ , so ist:
  1. Fn = $ \begin{pmatrix}
f_{n+1}&f_{n}\\
f_{n} &f_{n-1}
\end{pmatrix}$ und (f (n)| n $ \in$ $ \mbox{$\mathbb Z$}$) ist die Fibonaccifolge f0 = 0 und f1 = 1.
  2. det(Fn) = (- 1)n. Das heißt fn+1 . fn-1 - fn2 = (- 1)n
  3. F-n = (- 1)n$ \begin{pmatrix}
f_{n-1}&-f_{n}\\
-f_{n}& f_{n+1}
\end{pmatrix}$

Beweis:Zu 1. Es ist F = $ \begin{pmatrix}
f_{2}&f_{1}\\
f_{1}&f_{0}
\end{pmatrix}$ nach Definition. Erklärt man noch f-1 = 1, so ist die Behauptung auch für F0 erfüllt.

Gelte die Behauptung für Fn. Dann ist

Fn+1 = $\displaystyle \begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}$ . $\displaystyle \begin{pmatrix}
f_{n+1}&f_{n}\\
f_{n} &f_{n-1}
\end{pmatrix}$  
  = $\displaystyle \begin{pmatrix}
f_{n+1}+f_{n}&f_{n}+f_{n-1}\\
f_{n+1} &f_{n}
\end{pmatrix}$ = $\displaystyle \begin{pmatrix}
f_{n+2}&f_{n+1}\\
f_{n+1} &f_{n}
\end{pmatrix}$  

Zu 2. det(Fn) = (- 1)n = fn+1 . fn-1 - fn2.

Zu 3.

$\displaystyle \begin{pmatrix}
f_{n-1}&-f_{n}\\
-f_{n}&f_{n+1}
\end{pmatrix}$ . $\displaystyle \begin{pmatrix}
f_{n+1}&f_{n}\\
f_{n} &f_{n-1}
\end{pmatrix}$ = $\displaystyle \begin{pmatrix}
f_{n-1}f_{n+1}-f_{n}^{2}&f_{n}f_{n-1}-f_{n}f_{n-1}\\
-f_{n}f_{n+1}+ f_{n}f_{n+1} & -f_{n}^{2}+f_{n-1}f_{n+1}
\end{pmatrix}$  
  = $\displaystyle \begin{pmatrix}
(-1)^{n} & 0\\
0 & (-1)^{n}
\end{pmatrix}$ = (- 1)n . $\displaystyle \begin{pmatrix}
1 &0\\
0&1
\end{pmatrix}$  

$ \Box$

Folgerung 2.3   Für k $ \in$ $ \mbox{$\mathbb{N}$}$ gilt:
  1. $\displaystyle {\frac{{f_{2k+1}}}{{f_{2k}}}}$ > $\displaystyle {\frac{{f_{2k}}}{{f_{2k-1}}}}$
  2. $\displaystyle {\frac{{f_{2k+2}}}{{f_{2k+1}}}}$ < $\displaystyle {\frac{{f_{2k+1}}}{{f_{2k}}}}$
  3. $\displaystyle {\frac{{f_{2k}}}{{f_{2k-1}}}}$ < $\displaystyle {\frac{{f_{2k+2}}}{{f_{2k+1}}}}$

Beweis:Zu 1. $\displaystyle {\frac{{f_{2k+1}}}{{f_{2k}}}}$ - $\displaystyle {\frac{{f_{2k}}}{{f_{2k-1}}}}$ = $\displaystyle {\frac{{f_{2k+1}f_{2k-1}-f_{2k}^{2}}}{{f_{2k}f_{2k-1}}}}$ = $\displaystyle {\frac{{(-1)^{2k}}}{{f_{2k}f_{2k-1}}}}$ > 0. Genauso rechnet man 2. und 3. nach. $ \Box$
Wir haben daher die folgende Situation:

$\displaystyle {\frac{{f_{2}}}{{f_{1}}}}$ < $\displaystyle {\frac{{f_{4}}}{{f_{3}}}}$...$\displaystyle {\frac{{f_{2k}}}{{f_{2k-1}}}}$ < $\displaystyle {\frac{{f_{2k+1}}}{{f_{2k}}}}$...$\displaystyle {\frac{{f_{5}}}{{f_{4}}}}$ < $\displaystyle {\frac{{f_{3}}}{{f_{2}}}}$    

Links klettert man hoch rechts runter. Dazwischen wohnt eine besondere Zahl. Beide Folgen sind in die entsprechende Richtung beschränkt. Wegen der Vollständigkeit von $ \mbox{$\mathbb{R}$}$ konvergieren beide. Zu zeigen bleibt: Sie haben den gleichen Grenzwert:

Satz 2.4   Die Folge (an) = $ \left(\vphantom{\displaystyle \frac{f_{n+1}}{f_{n}}}\right.$$\displaystyle {\frac{{f_{n+1}}}{{f_{n}}}}$$ \left.\vphantom{\displaystyle \frac{f_{n+1}}{f_{n}}}\right)$ konvergiert. Ihren Grenzwert ist die größere Lösung der Gleichung x2 - x - 1 = 0. Also der Grenzwert ist $ \Phi$

Beweis:Wir wissen schon

$\displaystyle {\frac{{f_{2k+1}}}{{f_{2k}}}}$ - $\displaystyle {\frac{{f_{2k}}}{{f_{2k-1}}}}$ = $\displaystyle {\frac{{(-1)^{2k}}}{{f_{2k}f_{2k-1}}}}$    

Beachtet man noch, dass fn$ \ge$n ist, so folgt, dass die Differenz eine Nullfolge ist. Sei $ \alpha$ = $ \lim\limits_{{n\to \infty}}^{}$$ {\frac{{f_{n+1}}}{{f_{n}}}}$ Es ist

$\displaystyle {\frac{{f_{n+2}}}{{f_{n+1}}}}$ = $\displaystyle {\frac{{f_{n+1}+f_{n}}}{{f_{n+1}}}}$ = 1 + $\displaystyle {\frac{{f_{n}}}{{f_{n+1}}}}$    

Schreibt man den Limes davor so erhält man: $ \alpha$ = 1 + $ {\frac{{1}}{{\alpha}}}$. Daher ist $ \alpha$ = $ \Phi$.

$ \Box$

Folgerung 2.5   Ist $ \left(\vphantom{\begin{array}{c}
a_{n+1}\\
a_{n}\\
\end{array}}\right.$$ \begin{array}{c}
a_{n+1}\\
a_{n}\\
\end{array}$$ \left.\vphantom{\begin{array}{c}
a_{n+1}\\
a_{n}\\
\end{array}}\right)$ = Fn$ \left(\vphantom{\begin{array}{c}
a\\
b\\
\end{array}}\right.$$ \begin{array}{c}
a\\
b\\
\end{array}$$ \left.\vphantom{\begin{array}{c}
a\\
b\\
\end{array}}\right)$ mit beliebigem a, b > 0 $ \in$ $ \mbox{$\mathbb{R}$}$, so konvergiert die Folge $\displaystyle {\frac{{a_{n+1}}}{{a_{n}}}}$ gegen $ \Phi$.

Beweis:Es ist
$\displaystyle {\frac{{a_{n+1}}}{{a_{n}}}}$ = $\displaystyle {\frac{{f_{n+1}a+f_{n}b}}{{f_{n}a+f_{n-1}b}}}$  
  = $\displaystyle {\frac{{\frac{f_{n+1}}{fn}a+b}}{{a+\frac{f_{n-1}}{fn}b}}}$  

Schreibt man lim davor, so erhält man: $ \lim\limits_{{{n\to\infty}}}^{}$$ {\frac{{a_{n+1}}}{{a_{n}}}}$ = $ {\frac{{\Phi a+b}}{{a+\frac{b}{\Phi}}}}$ = $ {\frac{{\Phi(a+\frac{b}{\Phi})}}{{(a+\frac{b}{\Phi})}}}$ = $ \Phi$. $ \Box$

Eine Frage ist: Für welche Startwert lässt sich die goldene Folge beliebig anständig fortsetzen? Das heißt: Wann sind die weiteren Folgenglieder stets positiv?

Satz 2.6   Eine goldene Folge az = az+1 + az+2 enthält genau dann nur positive Glieder, wenn a0 > 0 und $ {\frac{{a_{0}}}{{a_{1}}}}$ = $ \Phi$ ist.

Beweis:Wir haben $ \left(\vphantom{\begin{array}{c}
a_{0}\\
a_{1}\\
\end{array}}\right.$$ \begin{array}{c}
a_{0}\\
a_{1}\\
\end{array}$$ \left.\vphantom{\begin{array}{c}
a_{0}\\
a_{1}\\
\end{array}}\right)$ = F$ \left(\vphantom{\begin{array}{c}
a_{1}\\
a_{2}\\
\end{array}}\right.$$ \begin{array}{c}
a_{1}\\
a_{2}\\
\end{array}$$ \left.\vphantom{\begin{array}{c}
a_{1}\\
a_{2}\\
\end{array}}\right)$... = Fn$ \left(\vphantom{\begin{array}{c}
a_{n}\\
a_{n+1}\\
\end{array}}\right.$$ \begin{array}{c}
a_{n}\\
a_{n+1}\\
\end{array}$$ \left.\vphantom{\begin{array}{c}
a_{n}\\
a_{n+1}\\
\end{array}}\right)$. Also ist

F-n$\displaystyle \left(\vphantom{\begin{array}{c} a_{0}\\  a_{1}\\  \end{array}}\right.$$\displaystyle \begin{array}{c} a_{0}\\  a_{1}\\  \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} a_{0}\\  a_{1}\\  \end{array}}\right)$ = $\displaystyle \left(\vphantom{\begin{array}{c} a_{n}\\  a_{n+1}\\  \end{array}}\right.$$\displaystyle \begin{array}{c} a_{n}\\  a_{n+1}\\  \end{array}$$\displaystyle \left.\vphantom{\begin{array}{c} a_{n}\\  a_{n+1}\\  \end{array}}\right)$.    

Beide Komponenten sind > 0.

F-n = (- 1)n$\displaystyle \begin{pmatrix}f_{n-1}&-f_{n}\\  -f_{n}&f_{n+1} \end{pmatrix}$    

Für alle geraden n folgt
fn-1 . a0 - fn . a1 = an > 0  
$\displaystyle {\frac{{a_{0}}}{{a_{1}}}}$ > $\displaystyle {\frac{{f_{n}}}{{f_{n-1}}}}$  
- fn . a0 + fn+1 . a1 = an+1 > 0  
$\displaystyle {\frac{{a_{0}}}{{a_{1}}}}$ < $\displaystyle {\frac{{f_{n+1}}}{{f_{n}}}}$  

Dies gilt für alle geraden n. Der Grenzwert beider Seiten ist $ \Phi$. Also ist $ {\frac{{a_{0}}}{{a_{1}}}}$ = $ \Phi$. $ \Box$
Der Homomorphismus F operiert transitiv auf der Geraden $ \left(\vphantom{\begin{array}{c}
\Phi\\
1\\
\end{array}}\right.$$ \begin{array}{c}
\Phi\\
1\\
\end{array}$$ \left.\vphantom{\begin{array}{c}
\Phi\\
1\\
\end{array}}\right)$$ \mbox{$\mathbb{R}$}$ = U. Der Unterraum U ist abgeschlossen gegenüber F und F-1 und damit abgeschlossen gegenüber jedem Homomorphismus der Form Id$ \alpha$ + F$ \beta$ mit $ \alpha$,$ \beta$ $ \in$ $ \mbox{$\mathbb{R}$}$.

Aufgaben:

  1. fn$ \le$$ \Phi^{{n-1}}_{}$ für alle n $ \in$ $ \mbox{$\mathbb{N}$}$.
  2. fn+m = fmfn+1 + fm-1fn
  3. fn . k ist Vielfaches von fk
  4. ggT(fm, fn) = fggT(m, n). Dabei ist ggT(a, b) der größte gemeinsame Teiler von a und b.
  5. Es sei $ \Phi$ = $ {\frac{{1+\sqrt{5}}}{{2}}}$ die größere Lösung der Gleichung x2 - x - 1 = 0. Und $ \overline{{\Phi}}$ die kleinere Lösung dieser Gleichung: Man zeige:
    1. K = $ \mbox{$\mathbb Q$}$[$ \Phi$] ist ein Körper und $ \alpha$ : K $ \ni$ a + b$ \Phi$ $ \mapsto$ a + b$ \overline{{\Phi}}$ $ \in$ K ist der einzige Automorphismus $ \neq$ Id, der $ \mbox{$\mathbb Q$}$ festlässt.
    2. fn = $\displaystyle {\frac{{\Phi^{n}-\overline{\Phi}^{n}}}{{\Phi-\overline{\Phi}}}}$.
    3. Die Folge an = $\displaystyle {\frac{{\Phi^{n}+\overline{\Phi}^{n}}}{{\Phi+\overline{\Phi}}}}$ ist eine Folge natürlicher Zahlen, mit der Fibonaccieigenschaft. Sie heißt zugehörige Lucas Folge.

  6. Sei f : $ \mbox{$\mathbb{R}$}$ $ \setminus$ 0 $ \rightarrow$ $ \ni$ x $ \mapsto$ $\displaystyle {\frac{{x+1}}{{x}}}$ $\displaystyle \in$ $\displaystyle \mbox{$\mathbb{R}$}$. Man definiert rekursiv eine Folge a0 = 1 und an+1 : = f (an). Konvergiert die Folge? Wenn ja spielt der Startwert eine Rolle? Wie sieht es bei negativen Startwerten aus?
  7. Eine Fülle weiterer Aufgaben findet man in [Knu73, Seite 78 ff]
Andreas Bartholome
2004-10-27