Fibonacci-Folge

Die Fibonacci-Folge ist eine mathematische Folge von nichtnegativen ganzen Zahlen, den Fibonacci-Zahlen.

Zur Entstehung des Namens

Ihre früheste Erwähnung findet sich unter dem Namen maatraameru („Berg der Kadenz“) in der Chhandah-shāstra („Kunst der Prosodie“) des Sanskrit-Grammatikers Pingala (um 450 oder nach anderer Datierung um 200 v. Chr.). . In ausführlicherer Form behandelten später auch Virahanka (6. Jh.) und besonders dann Acharya Hemachandra (1089–1172) diese Zahlenfolge, um die rechnerische Möglichkeit der Bildung von Metren durch regelmäßige Verteilung kurzer und langer Silben zu beschreiben.

In der westlichen Welt war es zuerst der italienische Mathematiker Leonardo da Pisa, genannt Fibonacci („figlio di Bonacci“, Sohn des Bonacci), der in seinem Liber abbaci („Buch der Rechenkunst“, Erstfassung von 1202 nicht erhalten, 2. Fassung von ca. 1227) diese Zahlenfolge mit dem Beispiel eines Kaninchenzüchters beschrieb, der herausfinden will, wie viele Kaninchenpaare innerhalb eines Jahres aus einem einzigen Paar entstehen, wenn jedes Paar ab dem zweiten Lebensmonat ein weiteres Paar pro Monat zur Welt bringt. Nachdem spätere Mathematiker wie Gabriel Lamé (1795-1870) die Entdeckung dieser Zahlenfolge für sich beansprucht hatten, brachten Edouard Lucas (1842-1891) und andere wieder in Erinnerung, dass der zu dieser Zeit älteste bekannte Beleg von Leonardo da Pisa stammte, und unter dem Namen „Fibonacci-Folge“ („série de Fibonacci“, „Fibonacci sequence“, „successione di Fibonacci“) ist sie seither in den meisten westlichen Sprachen geläufig geworden.

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, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269. ..

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.

Ob nun das rekursive Bildungsgesetz oder die Formel von Binet als Definition herangezogen wird, hängt maßgeblich von der zu lösenden Aufgabenstellung ab.

Modell einer Kaninchenpopulation

Fibonacci illustriert diese Folge durch die einfache mathematischen Modellierung des Wachstums einer Kaninchenpopulation nach folgender Vorschrift:

1. Zu Beginn gibt es ein Paar geschlechtsreifer Kaninchen.
2. Jedes neugeborene Paar wird im zweiten Lebensmonat geschlechtsreif.
3. Jedes geschlechtsreife Paar wirft pro Monat ein weiteres Paar.
4. Die Tiere befinden sich in einem abgeschlossenen Raum („in quodam loco, qui erat undique pariete circundatus“), so dass kein Tier die Population verlassen und keines von außen hinzukommen kann.

Das erste Paar erzeugt bei Fiobonacci seinen Nachwuchs bereits im ersten Monat. Jeden Folgemonat kommt dann 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. Fibonacci führt den Sachverhalt für die 12 Monate eines Jahres vor (1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377) und weist auf die Bildung der Reihe durch Addition mit dem jeweils vorhergehenden Reihenglied hin (1+2=3, 2+3=5, 3+5=8, etc.). Er merkt außerdem an, dass die Folge sich (unter der Annahme unsterblicher Kaninchen) unendlich fortsetzen lässt: „et sic posses facere per ordinem de infinitis numeris mensibus.“ Weitere Beachtung hat er dem Prinzip in seinen erhaltenen Werken nicht geschenkt.

Formel von Binet

Die Fibonacci-Zahlen lassen sich auch direkt über eine Formel berechnen:

${f_{n}={\frac {\Phi ^{n}-\Psi ^{n}}{\Phi \;\;-\Psi \;\;}};}\qquad {n\in \mathbb {Z} ;}\qquad {\Phi ={\frac {1+{\sqrt {5}}}{2}};}\qquad {\Psi ={\frac {1-{\sqrt {5}}}{2}}.}$

Mit dem Goldenen Schnitt $\Phi$ und seinem negativen Reziprokwert $\Psi$ eingesetzt, ergibt dies die ursprünglich vom französischen Mathematiker Jacques Philippe Marie Binet anno 1843 veröffentlichte Formel:

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

Bemerkenswert ist das Zusammenspiel zweier irrationaler Zahlen ${\lbrace \Phi ,\Psi \rbrace }$, welches zu einem ganzzahligen Ergebnis führt. 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 ${\lbrace \Phi ,\Psi \rbrace }$ und führt später zur obigen 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. Deshalb 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.

Der Absolutbetrag des Quotienten $\Psi ^{n}/{\sqrt {5}}\approx (-0,618033989)^{n}/{\sqrt {5}}$ ist für alle n kleiner als 0,5. Demnach beschreibt die Näherungsformel das exakte Ergebnis mit einem Fehler von weniger als 0,5. Durch Runden kommt man daher wieder zu einer exakten Formel:

$f_{n}=\left\lfloor {\frac {1}{\sqrt {5}}}{\Phi }^{n}+{\frac {1}{2}}\right\rfloor =\left\lfloor {\frac {1}{\sqrt {5}}}\cdot \left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}\right\rfloor$

mit der Gauß-Klammer $\lfloor {\cdot }\rfloor$.

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.

Identität von Catalan:

• $f_{n}^{2}-f_{n+k}\;f_{n-k}=(-1)^{n-k}f_{k}^{2}$

Identität von Cassini, Spezialfall der Catalan-Identität:

• $f_{n+1}\;f_{n-1}-f_{n}^{2}=(-1)^{n}$

Identität von d'Ocagne:

• $f_{m}\;f_{n+1}-f_{n}\;f_{m+1}=(-1)^{n}f_{m-n}$

Weitere Beziehungen:

• $f_{n}^{2}+f_{n+1}^{2}=f_{2n+1}$
• $f_{n+1}^{2}-f_{n-1}^{2}=f_{2n}$
• $f_{2n+1}^{2}=f_{2n}^{2}+f_{2n}f_{2n+1}+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 auf der linken Seite stehende Potenzreihe konvergiert für $|z|<1/\Phi$.

Darstellung mit Matrizen

Die Fibonacci-Zahlen tauchen auch als Einträge der Potenzen der Matrix $A={\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}$. $A$ beschreibt zugleich die Summationsvorschrift der Fibonacci-Folge, denn ihr Produkt mit einem Paar aufeinanderfolgender Fibonacci-Zahlen (als Spaltenmatrix geschrieben) ergibt das nächste Paar; entsprechend erzeugt $A^{n}$ das $n$-te Paar aus dem Startpaar $(0,1)$. Dies und die Tatsache, dass die Eigenwerte von $A$ gerade der Goldene Schnitt und dessen Kehrwert (letzterer mit negativem Vorzeichen) sind, führen wieder auf die oben genannte Formel von Binet.

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.

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 Rock-Band Tool bedient sich in ihrem Song „Lateralus“ (vom gleichnamigen Album von 2001) der Fibonacci-Folge und lässt die Silben der Strophentexte im entsprechenden Rhythmus erklingen.

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

• Fibonacci-Zahlen in der Online-Enzyklopädie der Zahlenfolgen
• 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
• 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)
• Diagrama de flujo que realiza la secuencia de Fibonacci (Flussdiagramm zur Fibonacci-Folge)
• Berechnung der Fibonacci-Folge in C#
• Facharbeit über die Fibonaccizahlen