Fibonacci-Folge

Ein Kachelmuster aus Quadraten, deren Kantenlängen der Fibonacci-Folge entsprechen.

Die Fibonacci-Folge ist eine unendliche Folge von Zahlen (den Fibonacci-Zahlen), bei der sich die jeweils folgende Zahl durch Addition ihrer beiden vorherigen Zahlen ergibt: 0, 1, 1, 2, 3, 5, 8, 13, … Benannt ist sie nach Leonardo Fibonacci, der damit 1202 das Wachstum einer Kaninchenpopulation beschrieb. Die Folge war aber schon in der Antike sowohl den Griechen als auch den Indern^[1] bekannt.

Definition der Fibonacci-Folge

Die Fibonacci-Folge $ f_{0},\,f_{1},\,f_{2},\,\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: (Folge A000045 in OEIS)

n	fn	n	fn	n	fn	n	fn	n	fn
0	0	10	55	20	6.765	30	832.040	40	102.334.155
1	1	11	89	21	10.946	31	1.346.269	41	165.580.141
2	1	12	144	22	17.711	32	2.178.309	42	267.914.296
3	2	13	233	23	28.657	33	3.524.578	43	433.494.437
4	3	14	377	24	46.368	34	5.702.887	44	701.408.733
5	5	15	610	25	75.025	35	9.227.465	45	1.134.903.170
6	8	16	987	26	121.393	36	14.930.352	46	1.836.311.903
7	13	17	1.597	27	196.418	37	24.157.817	47	2.971.215.073
8	21	18	2.584	28	317.811	38	39.088.169	48	4.807.526.976
9	34	19	4.181	29	514.229	39	63.245.986	49	7.778.742.049

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 nicht sinnvoll interpretiert werden kann.

Die Folge kann über die Rekursion

$ f_{n-2}=f_{n}-f_{n-1}\ $

auch in den Bereich mit negativem Index n erweitert werden. Es gilt die Beziehung

$ f_{-n}=(-1)^{n+1}f_{n}\ . $

Die in den negativen Indexbereich erweiterte Fibonacci-Folge lautet dann

$ \ldots ,\;-8,\;5,\;-3,\;2,\;-1,\;1,\;0,\;1,\;1,\;2,\;3,\;5,\;8,\;\ldots $

Darüber hinaus ist eine Verallgemeinerung der Fibonacci-Zahlen auf komplexe Zahlen und auf Vektorräume möglich.

Eigenschaften

Beziehungen zwischen den Folgegliedern

Identitäten:

• $ 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}) $
• $ f_{2n+1}=f_{n}^{2}+f_{n+1}^{2} $
• $ f_{n}^{2}-f_{n+k}\;f_{n-k}=(-1)^{n-k}f_{k}^{2} $ (Identität von Catalan)
• $ f_{n+1}\;f_{n-1}-f_{n}^{2}=(-1)^{n} $ (Identität von Cassini, Spezialfall der Catalan-Identität)
• $ f_{m}\;f_{n+1}-f_{n}\;f_{m+1}=(-1)^{n}f_{m-n} $ (Identität von d’Ocagne)

Teilbarkeit:

• $ \operatorname {ggT} (f_{m},f_{n})=f_{\operatorname {ggT} (m,n)} $
• Je zwei benachbarte Fibonaccizahlen sind teilerfremd, d. h. $ \operatorname {ggT} (f_{n},f_{n+1})=1 $.
• $ 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.
• $ 2\mid f_{n}\Leftrightarrow 3\mid n $ (genau jede dritte Fibonacci-Zahl ist durch 2 teilbar)
• $ 3\mid f_{n}\Leftrightarrow 4\mid n $ (genau jede vierte Fibonacci-Zahl ist durch 3 teilbar)
• $ 4\mid f_{n}\Leftrightarrow 6\mid n $ (genau jede sechste Fibonacci-Zahl ist durch 4 teilbar)
• $ 5\mid f_{n}\Leftrightarrow 5\mid n $ (genau jede fünfte Fibonacci-Zahl ist durch 5 teilbar)
• $ 7\mid f_{n}\Leftrightarrow 8\mid n $ (genau jede achte Fibonacci-Zahl ist durch 7 teilbar)
• $ 16\mid f_{n}\Leftrightarrow 12\mid n $ (genau jede zwölfte Fibonacci-Zahl ist durch 16 teilbar)^[2]

Für die Teilbarkeit durch Primzahlen p gilt unter Verwendung des Jacobi-Symbols:

• $ p\mid f_{p-1}\Leftrightarrow \left({\frac {5}{p}}\right)=1 $
• $ p\mid f_{p+1}\Leftrightarrow \left({\frac {5}{p}}\right)=-1 $^[3]

Reihen:

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

Es gibt noch zahlreiche weitere derartige Formeln.

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 der Näherungsformel für große n:

$ \lim _{n\to \infty }{\frac {f_{n+1}}{f_{n}}}=\lim _{n\to \infty }{\Phi ^{n+1} \over \Phi ^{n}}=\Phi \approx 1{,}618\ldots $

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+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\dotsb }}}}}}}} $

darstellen.

Φ ist eine irrationale Zahl. Das bedeutet, dass sie sich nicht durch ein Verhältnis zweier ganzer Zahlen darstellen 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. Dies gilt auch für verallgemeinerte Fibonaccifolgen, bei denen $ f_{0} $ und $ f_{1} $ beliebige natürliche Zahlen annehmen.

Zeckendorf-Theorem

Das nach Edouard Zeckendorf benannte Zeckendorf-Theorem 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=2}^{k}c_{i}f_{i}\quad \ c_{i}\in \{0,1\};\forall i:c_{i}c_{i+1}=0 $

Die entstehende Folge $ (c)_{i} $ von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Da aufeinanderfolgende Fibonacci-Zahlen ausgeschlossen sind, können keine zwei Einsen in einer Zeckendorf-Sequenz unmittelbar hintereinander stehen.

Allgemeiner ist die verwandte Aussage, dass sich jede ganze Zahl z eindeutig als Summe verschiedener, nicht direkt aufeinanderfolgender negaFibonacci-Zahlen ($ f_{-k} $ mit $ k\geq 1 $) darstellen lässt.

$ z=\sum _{i=1}^{k}c_{i}f_{-i}\quad \ c_{i}\in \{0,1\};\forall i:c_{i}c_{i+1}=0 $

So wäre zum Beispiel $ -2=f_{-1}+f_{-4}=1-3 $ als Binärsequenz 1001 darstellbar.^[4]

Fibonacci-Folgen in der Natur

Sonnenblume mit 34 und 55 Fibonacci-Spiralen

Anordnung gleich großer Kreise im Abstand des goldenen Winkels mit farblicher Markierung der Fibonacci-Spiralen 8, 13, 21, 34.

Viele Pflanzen weisen in der Anordnung ihrer Blätter und anderer Teile 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. Durch diese spiralförmige Anordnung der Blätter um die Sprossachse erzielt die Pflanze die beste Lichtausbeute. Der Versatz der Blätter um das irrationale Verhältnis des Goldenen Winkels sorgt dafür, dass nie Perioden auftauchen, wie es z. B. bei 1/4 der Fall wäre (0° 90° 180° 270° | 0° 90° …). Dadurch wird der denkbar ungünstigste Fall vermieden, dass ein Blatt genau senkrecht über dem anderen steht und sich so die jeweils übereinanderstehenden Blätter maximalen Schatten machen oder maximale ‚Lichtlücken‘ entstehen.

Beispielsweise tragen die Köpfe der Silberdistel (Carlina acaulis) hunderte von gleichgestaltigen Blüten, die in kleineren Köpfen in einer 21 zu 55 Stellung, in größeren Köpfen in 34 zu 89 und 55 zu 144-Stellung in den Fruchtboden eingefügt sind.^[5] Auch die Schuppen von Fichtenzapfen wie auch von Ananasfrüchten bilden im und gegen den Uhrzeigersinn Spiralen, deren Schuppenanzahl durch zwei aufeinanderfolgende Fibonaccizahlen gegeben ist.^[6]

Wissenschaftshistorisch sei hier auf das Buch On Growth and Form von D’Arcy Wentworth Thompson (1917) verwiesen.

Ein weiterer interessanter Aspekt ist, dass die Fibonacci-Folge die Ahnenmenge einer männlichen (n=1) Honigbiene (Apis mellifera) beschreibt. Das erklärt sich dadurch, dass Bienendrohnen sich aus unbefruchteten Eiern entwickeln, die in ihrem Genom dem Erbgut der Mutter (n=2) entsprechen, welche wiederum zwei Eltern besitzt (n=3), usw.

Berechnung

Formel von Moivre-Binet

Die Fibonacci-Folge (rot) als Differenz zweier Folgen mit irrationalen Gliedern (schwarz).

Das explizite Bildungsgesetz für die Glieder der Fibonacci-Folge wurde unabhängig voneinander von den französischen Mathematikern Abraham de Moivre im Jahr 1718 und Jacques Philippe Marie Binet im Jahr 1843 entdeckt. Dazwischen war sie aber auch den Mathematikern Leonhard Euler und Daniel Bernoulli bekannt, letzterer lieferte 1728 auch den vermutlich ersten Beweis.^[7]

Die Fibonacci-Zahlen lassen sich direkt mittels

$ f_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }},\qquad n\in \mathbb {Z} $

berechnen, wobei $ \varphi ,\psi $ die beiden Lösungen der charakteristischen Gleichung $ x^{2}-x-1=0 $ sind und somit auch $ \varphi =\Phi $ und $ \psi =-\Phi ^{-1} $ gilt. Setzt man

$ \varphi ={\frac {1+{\sqrt {5}}}{2}} $     und     $ \psi =1-\varphi ={\frac {1-{\sqrt {5}}}{2}} $

ein, erhält man die explizite Formel von Moivre-Binet

$ f_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}={\frac {1}{\sqrt {5}}}\left[\Phi ^{n}-\left(-{\frac {1}{\Phi }}\right)^{n}\right]={\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 φ und ψ, das zu einem ganzzahligen Ergebnis führt. Die Abbildung zeigt die beiden Teilfolgen mit φ und ψ sowie deren Differenz. Der Einfluss von ψⁿ geht rasch gegen Null. Das kann man verwenden, um die Berechnung zu beschleunigen, indem man den Term ignoriert und das Ergebnis zur nächstgelegenen natürlichen Zahl rundet.

Induktiver Beweis

Einer der einfachsten Beweise gelingt induktiv. Wegen $ {\tfrac {\varphi ^{0}-\psi ^{0}}{\sqrt {5}}}=0=f_{0} $ und $ {\tfrac {\varphi ^{1}-\psi ^{1}}{\sqrt {5}}}=1=f_{1} $ ist der Induktionsanfang erfüllt. Für den Induktionsschritt sei die Formel schon bis n bewiesen und wir betrachten

$ f_{n-1}+f_{n}={\frac {\varphi ^{n-1}-\psi ^{n-1}+\varphi ^{n}-\psi ^{n}}{\sqrt {5}}}={\frac {\varphi ^{n}(1+{\frac {1}{\varphi }})-\psi ^{n}(1+{\frac {1}{\psi }})}{\sqrt {5}}}={\frac {\varphi ^{n+1}-\psi ^{n+1}}{\sqrt {5}}}=f_{n+1} $.

Dabei haben wir benutzt, dass $ \varphi $ und $ \psi $ der charakteristischen Gleichung $ x^{2}=x+1 $ bzw. $ 1+{\tfrac {1}{x}}=x $ genügen.

Herleitung der Formel von Moivre-Binet

Die Formel von Binet kann mit Matrizenrechnung und dem Eigenwertproblem in der Linearen Algebra hergeleitet werden mittels folgendem Ansatz:

$ {\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}={\begin{pmatrix}f(n)\\f(n+1)\end{pmatrix}},f(0)=0{\text{ und }}f(1)=1{\text{ mit }}n\geq 0. $

Nun transformiert man die Matrix $ A={\begin{pmatrix}0&1\\1&1\end{pmatrix}} $ in eine Diagonalmatrix $ D $ durch Betrachtung als Eigenwertproblem.

Es gilt $ A=TDT^{-1} $, wobei $ T $ die Matrix der Eigenvektoren und $ D $ die Diagonalmatrix mit den Eigenwerten ist. Damit folgt:

$ {\begin{aligned}{\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}&=A^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}=\left(TDT^{-1}\right)^{n}{\begin{pmatrix}f(0)\\f(1)\end{pmatrix}}=TD^{n}T^{-1}{\begin{pmatrix}0\\1\end{pmatrix}}\\&={\begin{pmatrix}{\frac {-1-{\sqrt {5}}}{2}}&{\frac {-1+{\sqrt {5}}}{2}}\\1&1\end{pmatrix}}{\begin{pmatrix}{\frac {1-{\sqrt {5}}}{2}}&0\\0&{\frac {1+{\sqrt {5}}}{2}}\end{pmatrix}}^{n}{\begin{pmatrix}-{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}-1}{2{\sqrt {5}}}}\\{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}+1}{2{\sqrt {5}}}}\end{pmatrix}}{\begin{pmatrix}0\\1\end{pmatrix}}\\&={\begin{pmatrix}{\frac {-1-{\sqrt {5}}}{2}}&{\frac {-1+{\sqrt {5}}}{2}}\\1&1\end{pmatrix}}{\begin{pmatrix}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}&0\\0&\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\end{pmatrix}}{\begin{pmatrix}-{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}-1}{2{\sqrt {5}}}}\\{\frac {1}{\sqrt {5}}}&{\frac {{\sqrt {5}}+1}{2{\sqrt {5}}}}\end{pmatrix}}{\begin{pmatrix}0\\1\end{pmatrix}}\\&={\begin{pmatrix}{\frac {-1-{\sqrt {5}}}{2}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}&{\frac {-1+{\sqrt {5}}}{2}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\\\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}&\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\end{pmatrix}}{\begin{pmatrix}{\frac {{\sqrt {5}}-1}{2{\sqrt {5}}}}\\{\frac {{\sqrt {5}}+1}{2{\sqrt {5}}}}\end{pmatrix}}\\&={\begin{pmatrix}-{\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\\-{\frac {1}{\sqrt {5}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\end{pmatrix}}\\&={\begin{pmatrix}{\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right]\\{\frac {1}{\sqrt {5}}}\left[\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n+1}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n+1}\right]\end{pmatrix}}\\&={\begin{pmatrix}f(n)\\f(n+1)\end{pmatrix}}\end{aligned}} $

Herleitung mittels Differenzengleichung

Eine andere Herleitungsmöglichkeit folgt aus der Theorie zu linearen Differenzengleichungen:

Sei $ C_{n}=x^{n},n\in \mathbb {N} _{0} $ eine geometrische Folge, so ergibt sich:

$ C_{n+1}-C_{n}-C_{n-1}=x^{n+1}-x^{n}-x^{n-1}=(x^{2}-x-1)x^{n-1} $

Wenn also $ x $ so gewählt wird, dass die charakteristische Gleichung $ x^{2}-x-1=0 $ erfüllt ist (also $ x=\varphi $ oder $ x=\psi \ $), wird $ C_{n+1}=C_{n}+C_{n-1} $, d. h., $ C_{n} $ erfüllt die Fibonacci-Rekursion mit dem Rekursionsanfang $ C_{0}=1 $ und $ C_{1}=x $.

Die rekursive Folge $ A_{0}=1 $, $ A_{1}=\varphi $, $ A_{n+1}=A_{n}+A_{n-1} $ hat die explizite Darstellung $ A_{n}=\varphi ^{n} $. Ebenso $ B_{0}=1 $, $ B_{1}=\psi \ $, $ B_{n}=\psi ^{n}\ $.

Mit $ A_{n} $ und $ B_{n} $ genügt durch die Superpositionseigenschaft auch jede Linearkombination $ L_{n}=\alpha A_{n}+\beta B_{n} $ der Fibonacci-Rekursion $ L_{n+1}=L_{n}+L_{n-1} $. Mit Hilfe eines linearen Gleichungssystems ergibt sich $ \alpha ={\tfrac {1}{\sqrt {5}}} $ und $ \beta =-{\tfrac {1}{\sqrt {5}}} $, damit $ L_{0}={\tfrac {\varphi ^{0}-\psi ^{0}}{\sqrt {5}}}=0=f_{0} $ und $ L_{1}={\tfrac {\varphi ^{1}-\psi ^{1}}{\sqrt {5}}}=1=f_{1} $. Folglich ergibt sich explizit $ F_{n}={\tfrac {A_{n}-B_{n}}{\sqrt {5}}}={\tfrac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}} $.

Für $ \alpha =\beta =1 $ ergibt sich $ L_{0}=2 $ und $ L_{1}=1 $, d. h. die klassische Lucas-Folge mit explizit $ L_{n}=A_{n}+B_{n}=\varphi ^{n}+\psi ^{n} $.

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 =0,618... $. Über die Partialbruchzerlegung erhält man wiederum die Formel von Moivre-Binet.

Durch Entwicklung der obigen Erzeugenden Funktion $ \textstyle {\frac {z}{1-z-z^{2}}}=z\cdot {\frac {1}{1-(z+z^{2})}} $ in eine Potenzreihe um $ z=0 $ ergibt sich durch Koeffizientenvergleich ein Zusammenhang zwischen den Fibonacci-Zahlen und den Binomialkoeffizienten. Dies gelingt durch Einsetzen des Polynoms $ w=z+z^{2} $ in die Potenzreihe für $ {\tfrac {1}{1-w}} $ mit $ |z|<1/\Phi $ und somit $ |w|<1 $.

Nach Multiplikation mit z ergibt sich $ \textstyle z\sum _{l\geq 0}(z+z^{2})^{l}=\sum _{l\geq 0}z^{l+1}\sum _{k=0}^{l}{\tbinom {l}{k}}z^{k} $, nach Umformen dieser Summe zu einer Binomialreihe.

Die letzte Summe kann mittels Umbenennung der Summationsindizes vereinfacht werden zu $ \textstyle \sum _{0\leq k\leq l}{\tbinom {l}{k}}z^{l+k+1}=\sum _{n\geq 0}z^{n}\sum _{k=0}^{n}{\tbinom {n-k-1}{k}} $.

Koeffizientenvergleich liefert schließlich $ \textstyle f_{n}=\sum _{k=0}^{n}{\tbinom {n-k-1}{k}} $.

Alternativ ergibt sich über die Definition $ \textstyle G(z):={\frac {z}{1-z-z^{2}}} $ die Darstellung

$ f_{n}={\frac {1}{n!}}{\frac {\mathrm {d} ^{n}}{\mathrm {d} z^{n}}}G(0). $

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.

Näherungsformel für große Zahlen

Für große Werte von n wird $ \psi ^{n}=\left({\tfrac {1-{\sqrt {5}}}{2}}\right)^{n} $ in der Formel von Binet immer kleiner, da der Ausdruck in der Klammer vom Betrag $ <1 $ ist. 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} $

Der Absolutbetrag des Quotienten $ {\tfrac {\psi ^{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 $.

Verallgemeinerungen

Die klassische („kanonische“) Fibonacci-Folge ist durch drei Kriterien charakterisiert:

• Eine lineare Iteration, welche die beiden vorangehenden Folgenglieder einbezieht
• Eine Linearkombination dieser Folgenglieder, in der beide Vorgänger den Koeffizienten +1 tragen
• Beide Startglieder gleich +1

Jedes dieser Kriterien erlaubt eine Verallgemeinerung:

• Die Wahl anderer Startglieder $ u\!\, $ und $ v\!\, $ liefert eine Folge $ <a_{n}>\!\, $, die mit der kanonischen Folge nach der Beziehung $ a_{n}\!\,=u\cdot f_{n-2}+v\cdot f_{n-1} $ zusammenhängt. Ein Beispiel hierfür ist die Lucas-Folge $ <L_{n}>\!\, $.

Für die Glieder einer solchen Folge gilt ein gegenüber der Formel von Moivre-Binet verallgemeinertes explizites Bildungsgesetz:

$ a_{n}\!\,={\frac {k\cdot \varphi ^{n}-l\cdot \psi ^{n}}{\sqrt {5}}} $ mit $ k\!\,=u\cdot \psi ^{2}-v\cdot \psi $ und $ l\!\,=u\cdot \varphi ^{2}-v\cdot \varphi $.

Die kanonische Folge stellt sich hier als Spezialfall mit u=v=1 dar, was wegen der charakteristischen Gleichung sofort k=1 und l=1 liefert.

• Die Wahl anderer Koeffizienten für die Linearkombination liefert eine Folge, für die eine andere charakteristische Gleichung gilt. Eine Folge mit der Iterationsvorschrift

$ a_{n}\!\,=q\cdot a_{n-2}+p\cdot a_{n-1} $

besitzt die charakteristische Gleichung $ x^{2}-px-q=\!\,0 $. Die Wurzeln dieser Gleichung bestimmen das explizite Bildungsgesetz. Wenn die charakteristische Gleichung die Wurzeln $ \alpha \!\, $ und $ \beta \!\, $ hat, dann lautet das Bildungsgesetz

$ a_{n}={\frac {k\cdot \alpha ^{n}-l\cdot \beta ^{n}}{\alpha -\beta }} $,

wobei k und l wieder durch die Startglieder bestimmt sind.

• Eine Iteration, die mehr als zwei vorangehende Folgenglieder einbezieht, besitzt dementsprechend ein Polynom höheren Grades als charakteristische Gleichung, wobei die Wurzeln $ \!\,x_{i} $ dieser Gleichung wieder im Bildungsgesetz auftauchen und die Koeffizienten $ \!\,k_{i} $ durch die Anfangswerte bestimmt sind. Es gilt dann

$ a_{n}=\sum _{i=1}^{n}{k_{i}x_{i}^{n}} $.

Eine Iteration, die nur das unmittelbar vorhergehende Glied verwendet, liefert in diesem Zusammenhang als entartete Fibonacci-Folge eine reine Potenzfolge.

Geschichte

Berechnung der Kaninchenaufgabe im Liber abbaci

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 v. Chr. oder nach anderer Datierung um 200 v. Chr.).^[8] 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 diese Reihe ebenfalls schon in der Antike Nikomachos von Gerasa (um 100 n. Chr.) bekannt.^[9] Sie ist aber mit dem Namen des italienischen Mathematikers Leonardo da Pisa, genannt Fibonacci („figlio di Bonacci“, Sohn des Bonacci), verbunden, der in seinem Liber abbaci („Buch der Rechenkunst“, Erstfassung von 1202 nicht erhalten, zweite 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:^[10]

Modell einer Kaninchenpopulation

Fibonacci illustrierte diese Folge durch die einfache mathematische Modellierung des Wachstums einer Population von Kaninchen nach folgenden Regeln:

1. Jedes Paar Kaninchen wirft pro Monat ein weiteres Paar Kaninchen.
2. Ein neugeborenes Paar bekommt erst im zweiten Lebensmonat Nachwuchs (die Austragungszeit reicht von einem Monat in den nächsten).
3. 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.

Fibonacci begann die Reihe, nicht ganz konsequent, nicht mit einem neugeborenen, sondern mit einem trächtigen Paar, das seinen Nachwuchs bereits im ersten Monat wirft, so dass im ersten Monat bereits 2 Paare zu zählen sind. In jedem Folgemonat kommt dann zu der Anzahl der Paare, die im Vormonat gelebt haben, eine Anzahl von neugeborenen Paaren hinzu, die gleich der Anzahl derjenigen Paare ist, die bereits im vorvergangenen Monat gelebt hatten, da der Nachwuchs des Vormonats noch zu jung ist, um jetzt schon seinerseits Nachwuchs zu werfen. Fibonacci führte den Sachverhalt für die zwölf Monate eines Jahres vor (2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377) und wies auf das Bildungsgesetz der Reihe durch Summierung jeweils zweier aufeinanderfolgender Reihenglieder (2+3=5, 3+5=8, 5+8=13 usw.) hin. Er merkte außerdem an, dass die Reihe sich nach diesem Prinzip für eine unendliche Zahl von Monaten fortsetzen lässt, was dann allerdings unsterbliche Kaninchen voraussetzt: „et sic posses facere per ordinem de infinitis numeris mensibus.“ Weitere Beachtung hatte er dem Prinzip in seinen erhaltenen Werken nicht geschenkt.

Nachdem spätere Mathematiker wie Gabriel Lamé (1795–1870) die Entdeckung dieser Zahlenfolge für sich beansprucht hatten, brachten Édouard Lucas (1842–1891)^[11] und andere wieder in Erinnerung, dass der zu dieser Zeit älteste bekannte Beleg von Leonardo da Pisa stammte, und unter dem Namen „Fibonacci-Folge“ („suite de Fibonacci“, „Fibonacci sequence“, „successione di Fibonacci“) ist sie seither in den meisten westlichen Sprachen geläufig.

Rezeptionen in Kunst und Unterhaltung

Martina Schettina: Fibonaccis Traum, 2008, 40 x 40 cm

• Das Systemgedicht alfabet (1981) der dänischen Schriftstellerin Inger Christensen basiert auf der Fibonacci-Folge.
• Das Cover des Debütalbums der kanadischen Band The Organ, Grab That Gun, wurde von David Cuesta mithilfe eines auf der Fibonacci-Folge basierenden Rasters entworfen.^[12]
• Der Künstler Mario Merz setzte sich in seinen Installationen mit der Fibonacci-Folge auseinander.
• Die Künstlerin Martina Schettina beschäftigt sich in ihren mathematischen Bildern ebenfalls mit den Fibonacci-Zahlen.^[13][14]
• Dan Brown verwendet in seinem Thriller The Da Vinci Code (2003) (deutsch: Sakrileg, 2004) die Fibonacci-Folge als geheime Botschaft.
• Im Film π – System im Chaos von Darren Aronofsky, in dem der Protagonist nach dem „Muster der Welt” in den Kursdaten von Aktien und in der Zahl π sucht, wird die Fibonacci-Folge erwähnt.

Siehe auch

• Fibonacci-Baum
• Fibonacci-Heap

Literatur

• John H. Conway und Richard K. Guy, The Book of Numbers, Copernicus NY 1996, ISBN 0-387-97993-X.
• Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. 2. Auflage. World Scientific, Singapur, 1999, ISBN 981-02-3264-0
• Huberta Lausch, Fibonacci und die Folge(n), Oldenbourg 2010, ISBN 978-3-486-58910-8.
• Paulo Ribenboim, The New Book of Prime Number Records, Springer-Verlag 1996, ISBN 0-387-94457-5.
• The Fibonacci Quarterly, seit 1963 vierteljährlich erscheinende Zeitschrift, die sich der Fibonacci- und verwandten Folgen widmet.

Weblinks

Wikibooks: Algorithmensammlung: Zahlentheorie: Fibonacci-Folge – Lern- und Lehrmaterialien

Commons: Fibonacci numbers – Sammlung von Bildern, Videos und Audiodateien

• Fibonacci-Zahlen – sehr ausführliche Seite mit weiterführenden Themen
• Fibonacci Numbers and the Golden Section (englisch)
• Fibonacci und der Goldene Schnitt (PDF; 1,22 MB)
• Video: Die Fibonacci-Zahlen (aus der Fernsehsendung Mathematik zum Anfassen des Senders BR-alpha) von Albrecht Beutelspacher
• Fibonacci-Faktor – Wie mit den Fibonacci-Zahlen Börsenkurse vorhergesagt werden
• Fibonacci Numbers and the Pascal Triangle (englisch, deutsch, serbisch)

Einzelnachweise