Fibonacci-Folge

Die Fibonacci-Folge ist eine mathematische Folge von nichtnegativen ganzen Zahlen, den Fibonacci-Zahlen. Der Mathematiker Leonardo Fibonacci (Leonardo von Pisa) entwickelte sie, um das Wachstum einer Population von Kaninchen zu beschreiben, und publizierte sie in seinem Buch "Liber Abaci" aus dem Jahre 1202.

Definition der Fibonacci-Folge

Die Fibonacci-Folge $(f_{0},f_{1},\ldots )$ ist durch das rekursive Bildungsgesetz

$f_{n}=f_{n-1}+f_{n-2}\$   für $n\geq 2$

mit den Anfangswerten

$f_{0}=0\$   und   $f_{1}=1\$

definiert. Das bedeutet in Worten:

• Für die beiden ersten Zahlen werden die Werte Null und Eins vorgegeben.
• Jede weitere Zahl ist die Summe ihrer beiden Vorgänger.

Daraus ergibt sich die Folge zu

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, ...

Oft wird auch $f_{0}=0$ ausgelassen und die Fibonacci-Folge mit $f_{1}=1$ und $f_{2}=1$ beginnend definiert, insbesondere bei der Anwendung auf Situationen, in denen ein Anfangswert Null keinen Sinn ergibt.

Modell einer Kaninchenpopulation

Fibonacci stieß auf diese Folge bei der einfachen mathematischen Modellierung des Wachstums einer Kaninchenpopulation nach folgender Vorschrift:

1. Zu Beginn gibt es ein Paar neugeborener Kaninchen.
2. Jedes neugeborene Kaninchenpaar wirft nach 2 Monaten ein weiteres Paar.
3. Anschließend wirft jedes Kaninchenpaar jeden Monat ein weiteres.
4. Kaninchen leben ewig und haben einen unbegrenzten Lebensraum.

Jeden Monat kommt zu der Anzahl der Paare, die im letzten Monat gelebt haben, eine Anzahl von neugeborenen Paaren hinzu, die gleich der Anzahl der Paare ist, die bereits im vorletzten Monat gelebt haben, da genau diese geschlechtsreif sind und sich nun vermehren. Dies entspricht der oben angegebenen Rekursionsformel.

Formel von Binet

Die Fibonacci-Zahlen lassen sich auch direkt über eine Formel berechnen, die der französische Mathematiker Jacques Philippe Marie Binet 1843 angegeben hat:

$f_{n}={\frac {1}{\sqrt {5}}}\left({\Phi }^{n}-{\Psi }^{n}\right)$ mit dem goldenen Schnitt $\Phi ={\frac {1+{\sqrt {5}}}{2}}$ und $\Psi =1-\Phi ={\frac {1-{\sqrt {5}}}{2}}$

Zusammen:

$f_{n}={\frac {1}{\sqrt {5}}}\left({\left({\frac {1+{\sqrt {5}}}{2}}\right)}^{n}-{\left({\frac {1-{\sqrt {5}}}{2}}\right)}^{n}\right)$

Im Unterschied zur Definition ist diese Formel nicht rekursiv.

Diese Formel lässt sich mit dem Ansatz $f(n)=a^{n}$ herleiten. Aus der Rekursionsformel folgt: $a^{2}=a+1$. Die Lösung dieser quadratischen Gleichung ergibt die obige Formel.

Näherungsformel für große n

Für große Werte von n wird der Ausdruck $\Psi ^{n}\approx (-0,618033989)^{n}$ in der Formel von Binet immer kleiner. Damit erhält man die Näherungsformel

$f_{n}\approx {\frac {1}{\sqrt {5}}}{\Phi }^{n}={\frac {1}{\sqrt {5}}}\cdot \left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\approx 0{,}4472135955\cdot 1{,}618033989^{n}$

Im Unterschied beispielsweise zur Stirling-Formel wird diese Formel für wachsende $n$ immer genauer; bei der Stirling-Formel geht lediglich der relative Fehler gegen 0.

Verwandtschaft mit dem Goldenen Schnitt

Wie von Johannes Kepler festgestellt wurde, nähert sich der Quotient zweier aufeinander folgender Fibonacci-Zahlen dem Goldenen Schnitt Φ an. Dies folgt unmittelbar aus obiger Näherungsformel für große n:

${\frac {f_{n+1}}{f_{n}}}\approx {\Phi ^{n+1} \over \Phi ^{n}}=\Phi \approx 1{,}618{...}$

Diese Quotienten zweier aufeinander folgender Fibonacci-Zahlen haben eine bemerkenswerte Kettenbruchdarstellung

${\frac {1}{1}}=1\qquad {\frac {2}{1}}=1+{\frac {1}{1}}\qquad {\frac {3}{2}}=1+{\frac {1}{1+{\frac {1}{1}}}}\qquad {\frac {5}{3}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}\qquad {\frac {8}{5}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}}}$

Da diese Quotienten im Grenzwert gegen den goldenen Schnitt konvergieren, lässt sich dieser als der unendliche Kettenbruch

$\Phi =1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+...}}}}}}}}$

darstellen.

Φ ist eine irrationale Zahl. Es zeigt sich, dass sie in einem bestimmten Sinne die irrationalste aller Zahlen ist. Das bedeutet, dass sie sich nur schlecht durch ein Verhältnis zweier ganzer Zahlen annähern lässt, ein Umstand, der wesentlich zu ihrer Bedeutung in Kunst und Natur beiträgt. Am besten lässt sich Φ durch Quotienten zweier aufeinander folgender Fibonacci-Zahlen darstellen.

Beziehungen zwischen den Folgegliedern

• $f_{m+n}=f_{n+1}\;f_{m}+f_{n}\;f_{m-1}$
• $f_{m+n}=f_{n}\;L_{m}+(-1)^{m+1}\;f_{n-m}$ mit der Lucas-Folge $L_{m}=f_{m+1}+\;f_{m-1}=\Phi ^{m}+\Psi ^{m}$, insbesondere:
• $f_{2n}=f_{n}\;L_{n}=f_{n}\;(f_{n+1}+f_{n-1})$
• $\operatorname {ggT} (f_{m},f_{n})=f_{\operatorname {ggT} (m,n)}$
• $m\mid n\implies f_{m}\mid f_{n}$; falls $m>2$ ist, gilt auch die Umkehrung. Insbesondere kann $f_{n}$ für $n>4$ nur dann eine Primzahl sein, wenn $n$ eine Primzahl ist.
• $f_{2n+1}^{2}=f_{2k}^{2}+f_{2k}f_{2k+1}$

Es gibt noch zahlreiche weitere derartige Formeln.

Erzeugende Funktion

Die erzeugende Funktion der Fibonacci-Zahlen ist

$\sum _{n=0}^{\infty }f_{n}z^{n}={\frac {z}{1-z-z^{2}}}.$

(Die Reihe konvergiert für $|z|<1/\Phi$.)

Darstellung mit Matrizen

Die Fibonacci-Zahlen tauchen auch als Einträge der Potenzen der Matrix ${\begin{pmatrix}1&1\\1&0\end{pmatrix}}$ auf:

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

Aus der Relation $A^{m+n}=A^{m}A^{n}$ ergibt sich beispielsweise die erste oben angegebene Formel für $f_{m+n}$.

Das Zeckendorf-Theorem

Das Zeckendorf-Theorem (nach Edouard Zeckendorf) besagt, dass jede natürliche Zahl n größer Null eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen geschrieben werden kann. Das heißt, es gibt für jedes $n\in \mathbb {N} ,n>0$ eine eindeutige Darstellung der Form

$n=\sum _{i=1}^{k}c_{i}f_{i},\qquad \ c_{i}\in \{0,1\}\$ mit $\ \forall i:c_{i}c_{i+1}=0$,

Die entstehende Folge $(c)$ von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Aus der Definition der Fibonacci-Zahlen folgt, dass keine zwei Einsen in einer Zeckendorf-Sequenz hintereinander stehen können.

Fibonacci-Folgen in der Natur

Sonnenblume mit 34 und 55 Fibonacci-Spiralen.

Reife Sonnenblume mit 89 und 144 Spiralen.

Viele Pflanzen weisen in ihrem Bauplan Spiralen auf, deren Anzahl durch Fibonacci-Zahlen gegeben sind, wie beispielsweise bei den Samen in Blütenständen. Das ist dann der Fall, wenn der Winkel zwischen architektonisch benachbarten Blättern oder Samen bezüglich der Pflanzenachse der Goldene Winkel ist. Hintergrund ist der Umstand, dass die rationalen Zahlen, die den zugrunde liegenden Goldenen Schnitt am besten approximieren, Brüche von aufeinanderfolgenden Fibonacci-Zahlen sind. Die Spiralen werden daher von Pflanzenelementen gebildet, deren Platznummern sich durch die Fibonacci-Zahl im Nenner unterscheiden und damit fast in die gleiche Richtung weisen.

Ein weiterer interessanter Aspekt ist, dass die Fibonacci-Folge die Ahnenmenge einer weiblichen Honigbiene (Apis mellifera) beschreibt. Das erklärt sich dadurch, dass Bienendrohnen sich aus unbefruchteten Eiern entwickeln, die in ihrem Genom dem Erbgut der Mutter entsprechen.

Trivia

Die Fibonacci-Folge spielt eine große Rolle in Dan Browns Roman „Sakrileg“.

Literatur

• Hans Magnus Enzensberger, Der Zahlenteufel, ISBN 3-446-18900-9
• John H. Conway und Richard K. Guy, The Book of Numbers, ISBN 0-387-97993-X
• Paolo Ribenboim, The New Book of Prime Number Records, ISBN 0-387-94457-5

Weblinks

• Schulprojekt über Fibonacci-Zahlen in der Mathematik und der Umwelt
• Sehr ausführliche und verständliche Darstellung
• Fibonacci-Zahlen bei Brettspielen
• Ausführliche Seite auf Englisch
• Weitere englische Seite mit Daten zu Leonardo Fibonacci
• Freies und plattformunabhängiges Programm, u. a. zur unbegrenzten Berechnung von Fibonacci-Zahlen (mit Java-Quelltext)
• Beweis des Zeckendorf-Theorems
• Fibonacci-Spiralen in der Botanik
• Fibonacci und der goldene Schnitt (pdf)