Fibonacci-Folge - de.LinkFang.org

Fibonacci-Folge




Die Fibonacci-Folge ist die unendliche Folge natürlicher Zahlen, die (ursprünglich) mit zweimal der Zahl 1 beginnt oder (häufig, in moderner Schreibweise) zusätzlich mit einer führenden Zahl 0 versehen ist.[1] Im Anschluss ergibt jeweils die Summe zweier aufeinanderfolgender Zahlen die unmittelbar danach folgende Zahl:

Die darin enthaltenen Zahlen heißen Fibonacci-Zahlen. Benannt ist die Folge nach Leonardo Fibonacci, der damit im Jahr 1202 das Wachstum einer Kaninchenpopulation beschrieb. Die Folge war aber schon in der Antike sowohl den Griechen als auch den Indern bekannt.[2]

Weitere Untersuchungen zeigten, dass die Fibonacci-Folge auch noch zahlreiche andere Wachstumsvorgänge in der Natur beschreibt. Es scheint, als sei sie eine Art Wachstumsmuster in der Natur.[3]

Die Fibonacci-Zahlen weisen einige bemerkenswerte mathematische Besonderheiten auf:

Inhaltsverzeichnis

Definition der Fibonacci-Folge


Die Fibonacci-Folge \({\displaystyle f_{1},\,f_{2},\,f_{3},\ldots }\) ist durch das rekursive Bildungsgesetz

\({\displaystyle f_{n}=f_{n-1}+f_{n-2}}\)   für   \({\displaystyle n\geq 3}\)

mit den Anfangswerten

\({\displaystyle f_{1}=f_{2}=1}\)

definiert.[4] Das bedeutet in Worten:

Daraus ergibt sich:

n fn n fn n fn n fn n fn
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
10 55 20 6 765 30 832 040 40 102 334 155 50 12 586 269 025

Aus der Forderung, dass die Rekursion

\({\displaystyle f_{n}=f_{n-1}+f_{n-2}}\)

auch für ganze Zahlen \({\displaystyle n\leq 2}\) gelten soll, erhält man eine eindeutige Fortsetzung auf den Index 0 und auf negative Indizes. Es gilt:

\({\displaystyle f_{0}=0}\)
\({\displaystyle f_{-n}=(-1)^{n+1}f_{n}}\) für alle \({\displaystyle n>0}\)

Die so erweiterte Fibonacci-Folge lautet dann

\({\displaystyle f_{-7}}\) \({\displaystyle f_{-6}}\) \({\displaystyle f_{-5}}\) \({\displaystyle f_{-4}}\) \({\displaystyle f_{-3}}\) \({\displaystyle f_{-2}}\) \({\displaystyle f_{-1}}\) \({\displaystyle f_{0}}\) \({\displaystyle f_{1}}\) \({\displaystyle f_{2}}\) \({\displaystyle f_{3}}\) \({\displaystyle f_{4}}\) \({\displaystyle f_{5}}\) \({\displaystyle f_{6}}\) \({\displaystyle f_{7}}\)
\({\displaystyle \dotsb }\) 13 −8 5 −3 2 −1 1 0 1 1 2 3 5 8 13 \({\displaystyle \dotsb }\)

und heißt Folge der negaFibonacci-Zahlen[5].

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

Eigenschaften


Verwandtschaft mit dem Goldenen Schnitt

Wie von Johannes Kepler festgestellt wurde, nähert sich der Quotient zweier aufeinanderfolgender Fibonacci-Zahlen dem Goldenen Schnitt \({\displaystyle \Phi }\) an. Dies folgt unmittelbar aus der Näherungsformel für große \({\displaystyle n}\):

\({\displaystyle \lim _{n\to \infty }{\frac {f_{n+1}}{f_{n}}}=\lim _{n\to \infty }{\Phi ^{n+1} \over \Phi ^{n}}=\Phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1{,}6180339887}\)

Diese Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen haben eine bemerkenswerte Kettenbruchdarstellung:

\({\displaystyle {\frac {1}{1}}=1\qquad {\frac {2}{1}}=1+{\frac {1}{1}}=[1;1]\qquad {\frac {3}{2}}=1+{\frac {1}{1+{\frac {1}{1}}}}=[1;1,1]\qquad {\frac {5}{3}}=1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1}}}}}}=[1;1,1,1]}\)

mit der \({\displaystyle [\,;\,]}\)-Notation aus endliche Kettenbrüche.

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

\({\displaystyle \Phi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{\;\,\ddots }}}}}}}}=[1;{\overline {1}}]}\)

darstellen. Die Zahl \({\displaystyle \Phi }\) ist irrational. Das bedeutet, dass sie sich nicht durch ein Verhältnis zweier ganzer Zahlen darstellen lässt. Am besten lässt sich \({\displaystyle \Phi }\) durch Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen approximieren. Dies gilt auch für verallgemeinerte Fibonaccifolgen, bei denen \({\displaystyle f_{0}}\) und \({\displaystyle f_{1}}\) beliebige natürliche Zahlen annehmen.

Beziehungen zwischen den Folgengliedern

Identitäten:

Teilbarkeit:

Für die Teilbarkeit durch Primzahlen \({\displaystyle p}\) gilt unter Verwendung des Jacobi-Symbols:

Reihen:

Es gibt noch zahlreiche weitere derartige Formeln.

Reziproke Reihe

Der Grenzwert der absolut konvergierenden reziproken Reihe der Fibonacci-Zahlen

ist irrational (André-Jeannin; 1989).[9]

Zudem zeigte Good (1974) und Hoggatt (1976):

Zeckendorf-Theorem

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

\({\displaystyle n=\sum _{i=2}^{k}c_{i}f_{i}}\) mit \({\displaystyle c_{i}\in \{0,1\}}\) und \({\displaystyle c_{i}c_{i+1}=0}\) für alle \({\displaystyle i}\).[11]

Die entstehende Folge \({\displaystyle \left(c_{i}\right)_{i\in 2+\mathbb {N} _{0}}}\) von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Sehr eng hängt damit der Fibonacci-Kode zusammen.

Berechnung


Formel von Moivre-Binet

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.[12]

Die Fibonacci-Zahlen lassen sich direkt mittels

\({\displaystyle f_{n}={\frac {\Phi ^{n}-\Psi ^{n}}{\Phi -\Psi }},\qquad n\in \mathbb {Z} }\)

berechnen, wobei \({\displaystyle \Phi ,\Psi }\) die beiden Lösungen der charakteristischen Gleichung \({\displaystyle x^{2}-x-1=0}\) sind. Mit

\({\displaystyle \Phi ={\frac {1+{\sqrt {5}}}{2}}}\)
\({\displaystyle \Psi =1-\Phi ={\frac {1-{\sqrt {5}}}{2}}=-\Phi ^{-1}}\)

ist explizit:

\({\displaystyle f_{n}={\frac {\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}={\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 \({\displaystyle \Phi }\) und \({\displaystyle \Psi }\), das zu einem ganzzahligen Ergebnis führt. Die Abbildung zeigt die beiden Teilfolgen mit \({\displaystyle \Phi }\) und \({\displaystyle \Psi }\) sowie deren Differenz.

Näherungsformel für große Zahlen

Der Einfluss von \({\displaystyle \Psi }\) geht rasch gegen Null, bspw. ist \({\displaystyle -5^{\scriptstyle -1/2}\Psi \approx +0{,}276}\). Das kann man verwenden, um die Berechnung abzukürzen, indem man den Term für genügend große \({\displaystyle n}\) ignoriert und das Ergebnis zur nächsten natürlichen Zahl rundet:

\({\displaystyle f_{n}={\Bigg \lfloor }{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+{\frac {1}{2}}{\Bigg \rfloor }=\left[{\frac {1}{\sqrt {5}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\right]}\)         (Gaußsche Rundungsklammer \({\displaystyle [\,\cdot \,]}\))

Tatsächlich geht das schon für \({\displaystyle 0\leq n\in \mathbb {Z} }\).

Induktiver Beweis

Einer der einfachsten Beweise gelingt induktiv. Wegen \({\displaystyle {\tfrac {\Phi ^{0}-\Psi ^{0}}{\sqrt {5}}}=0=f_{0}}\) und \({\displaystyle {\tfrac {\Phi ^{1}-\Psi ^{1}}{\sqrt {5}}}=1=f_{1}}\) ist der Induktionsanfang erfüllt. Angenommen, die Formel gelte für alle Werte von \({\displaystyle 0}\) bis \({\displaystyle n}\) (starke Induktionsvoraussetzung). Wir zeigen, dass sie dann notwendigerweise auch für \({\displaystyle n+1}\) gelten muss:

\({\displaystyle {\begin{aligned}f_{n-1}+f_{n}&={\frac {\Phi ^{n-1}-\Psi ^{n-1}+\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}\\&={\frac {\Phi ^{n-1}(1+\Phi )-\Psi ^{n-1}(1+\Psi )}{\sqrt {5}}}\\&={\frac {\Phi ^{n-1}(\Phi ^{2})-\Psi ^{n-1}(\Psi ^{2})}{\sqrt {5}}}\\&={\frac {\Phi ^{n+1}-\Psi ^{n+1}}{\sqrt {5}}}\\&=f_{n+1}\end{aligned}}}\)

Dabei haben wir benutzt, dass \({\displaystyle \Phi }\) und \({\displaystyle \Psi }\) der charakteristischen Gleichung \({\displaystyle x^{2}=x+1}\) genügen.

Nach dem Prinzip der vollständigen Induktion muss nun die Formel für alle \({\displaystyle n}\) gelten.

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:

\({\displaystyle {\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 \({\displaystyle A={\begin{pmatrix}0&1\\1&1\end{pmatrix}}}\) in eine Diagonalmatrix \({\displaystyle D}\) durch Betrachtung als Eigenwertproblem.

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

\({\displaystyle {\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 der linearen Differenzengleichungen:

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

\({\displaystyle 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 \({\displaystyle x}\) so gewählt wird, dass die charakteristische Gleichung \({\displaystyle x^{2}-x-1=0}\) erfüllt ist (also \({\displaystyle x=\Phi }\) oder \({\displaystyle x=\Psi \ }\)), wird \({\displaystyle C_{n+1}=C_{n}+C_{n-1}}\), d. h., \({\displaystyle C_{n}}\) erfüllt die Fibonacci-Rekursion mit dem Rekursionsanfang \({\displaystyle C_{0}=1}\) und \({\displaystyle C_{1}=x}\).

Die rekursive Folge \({\displaystyle A_{0}=1}\), \({\displaystyle A_{1}=\Phi }\), \({\displaystyle A_{n+1}=A_{n}+A_{n-1}}\) hat die explizite Darstellung \({\displaystyle A_{n}=\Phi ^{n}}\). Ebenso \({\displaystyle B_{0}=1}\), \({\displaystyle B_{1}=\Psi }\), \({\displaystyle B_{n}=\Psi ^{n}}\).

Mit \({\displaystyle A_{n}}\) und \({\displaystyle B_{n}}\) genügt wegen der Superpositionseigenschaft auch jede Linearkombination \({\displaystyle L_{n}=\alpha A_{n}+\beta B_{n}}\) der Fibonacci-Rekursion \({\displaystyle L_{n+1}=L_{n}+L_{n-1}}\). Mit Hilfe eines linearen Gleichungssystems ergibt sich \({\displaystyle \alpha ={\tfrac {1}{\sqrt {5}}}}\) und \({\displaystyle \beta =-{\tfrac {1}{\sqrt {5}}}}\), damit \({\displaystyle L_{0}={\tfrac {\Phi ^{0}-\Psi ^{0}}{\sqrt {5}}}=0=f_{0}}\) und \({\displaystyle L_{1}={\tfrac {\Phi ^{1}-\Psi ^{1}}{\sqrt {5}}}=1=f_{1}}\). Folglich ergibt sich explizit \({\displaystyle F_{n}={\tfrac {A_{n}-B_{n}}{\sqrt {5}}}={\tfrac {\Phi ^{n}-\Psi ^{n}}{\sqrt {5}}}}\).

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

Herleitung mittels z-Transformation

Da Differenzengleichungen sehr elegant mittels z-Transformation beschrieben werden können, kann man die z-Transformation auch zur Herleitung der expliziten Formel für Fibonacci-Zahlen einsetzen. Im Artikel Einsatz der z-Transformation zur Bestimmung expliziter Formeln von Rekursionsvorschriften wird die allgemeine Vorgehensweise beschrieben und dann am Beispiel der Fibonacci-Zahlenfolge erläutert.

Alternierende Näherung

Die Quotienten aufeinander folgender Glieder der Fibonacci-Folge sind abwechselnd kleiner und größer als der Goldene Schnitt:

\({\displaystyle {\frac {f_{2n}}{f_{2n-1}}}<\Phi <{\frac {f_{2n+1}}{f_{2n}}}}\)[13]

Herleitung  
.

Mithilfe der Formel von Moivre-Binet lässt sich eine einfach Herleitung angeben. Denn für die Zahlen \({\displaystyle \Phi ,\Psi }\) der genannten Formel und natürliche \({\displaystyle n>0}\) gilt:

\({\displaystyle -\Phi <0<-\Psi ;\qquad |\cdot \Psi ^{2n}>0}\)

\({\displaystyle -\Phi \Psi ^{2n}<-\Psi ^{2n+1};\qquad |+\Phi ^{2n+1}}\)

\({\displaystyle \Phi ^{2n+1}-\Phi \Psi ^{2n}=\Phi (\Phi ^{2n}-\Psi ^{2n})<\Phi ^{2n+1}-\Psi ^{2n+1};\qquad |:(\Phi ^{2n}-\Psi ^{2n})>0;\quad }\)(1)

\({\displaystyle \Phi <{\frac {\Phi ^{2n+1}-\Psi ^{2n+1}}{\Phi ^{2n}-\Psi ^{2n}}}={\frac {f_{2n+1}}{f_{2n}}}}\), da im Doppelbruch der Darstellung der Folgeglieder mit Moivre-Binet der gemeinsame Nenner \({\displaystyle \Phi -\Psi }\) verschwindet. - Entsprechend:

\({\displaystyle -\Phi <0<-\Psi ;\qquad |\cdot \Psi ^{2n-1}<0}\)

\({\displaystyle -\Phi \Psi ^{2n-1}>-\Psi ^{2n};\qquad |+\Phi ^{2n}}\)

\({\displaystyle \Phi ^{2n}-\Phi \Psi ^{2n-1}=\Phi (\Phi ^{2n-1}-\Psi ^{2n-1})>\Phi ^{2n}-\Psi ^{2n};\qquad |:(\Phi ^{2n-1}-\Psi ^{2n-1})>0}\)

\({\displaystyle \Phi >{\frac {\Phi ^{2n}-\Psi ^{2n}}{\Phi ^{2n-1}-\Psi ^{2n-1}}}={\frac {f_{2n}}{f_{2n-1}}};\quad }\) (2)

Die Ungleichungen (1) und (2) ergeben zusammen die Behauptung.

Die Differenz dieser oberen und unteren Schranke von \({\displaystyle \Phi }\) konvergiert für wachsende \({\displaystyle n}\) rasch gegen Null, denn:

\({\displaystyle {\frac {f_{2n+1}}{f_{2n}}}-{\frac {f_{2n}}{f_{2n-1}}}={\frac {f_{2n+1}f_{2n-1}-f_{2n}^{2}}{f_{2n}f_{2n-1}}}={\frac {1}{f_{2n}f_{2n-1}}}}\);

bei der Vereinfachung des Zählers wurde die Identität von Cassini nebst \({\displaystyle (-1)^{2n}=1}\) verwendet.

Erzeugende Funktion

Eine erzeugende Funktion der Fibonacci-Zahlen ist

\({\displaystyle \sum _{n=0}^{\infty }f_{n}z^{n}={\frac {z}{1-z-z^{2}}}={\frac {1}{\Phi -\Psi }}({\frac {1}{1-\Phi z}}-{\frac {1}{1-\Psi z}}).}\)

Die auf der linken Seite stehende Potenzreihe konvergiert für \({\displaystyle |z|<1/\Phi =0{,}618\ldots }\). Über die angegebene Partialbruchzerlegung erhält man wiederum die Formel von de Moivre-Binet.

Herleitung der erzeugenden Funktion  

Für \({\displaystyle G(z)=\sum _{n=0}^{\infty }f_{n}z^{n}}\) ist

\({\displaystyle \sum _{n=0}^{\infty }f_{n+1}z^{n}=\sum _{n=1}^{\infty }f_{n}z^{n-1}=z^{-1}\sum _{n=1}^{\infty }f_{n}z^{n}=z^{-1}\sum _{n=0}^{\infty }f_{n}z^{n}={\frac {G(z)}{z}}\quad }\), da \({\displaystyle f_{0}=0}\);

\({\displaystyle \sum _{n=0}^{\infty }f_{n+2}z^{n}=\sum _{n=2}^{\infty }f_{n}z^{n-2}=z^{-2}\sum _{n=2}^{\infty }f_{n}z^{n}=z^{-2}(-z+\sum _{n=0}^{\infty }f_{n}z^{n})={\frac {G(z)-z}{z^{2}}}\quad }\),da \({\displaystyle f_{0}=0}\) und \({\displaystyle f_{1}=1}\);

die Rekursionsbedigung \({\displaystyle f_{n+2}=f_{n+1}+f_{n}}\) induziert daher

\({\displaystyle \sum _{n=0}^{\infty }f_{n+2}z^{n}=\sum _{n=0}^{\infty }f_{n+1}z^{n}+\sum _{n=0}^{\infty }f_{n}z^{n}\Leftrightarrow }\)

\({\displaystyle {\frac {G(z)-z}{z^{2}}}={\frac {G(z)}{z}}+G(z)\quad \mid \cdot z^{2}}\)

\({\displaystyle G(z)-z=z\cdot G(z)+z^{2}\cdot G(z)\quad \mid }\); zusammenfassen:

\({\displaystyle G(z)\cdot (1-z-z^{2})=z}\),

mit Division durch \({\displaystyle (1-z-z^{2})\neq 0}\) (wahr geeignet gewählte \({\displaystyle z}\)) folgt die angegebene Form.

Mit einer geeigneten erzeugenden Funktion lässt sich ein Zusammenhang zwischen den Fibonacci-Zahlen und den Binomialkoeffizienten darstellen:

\({\displaystyle f_{n\geq 1}=\sum _{k=0}^{[{\frac {n-1}{2}}]}{\tbinom {n-k-1}{k}}}\).

Wegen \({\displaystyle \textstyle {\tbinom {n-k-1}{k}}=0}\) für \({\displaystyle \textstyle n-k-1\geq 0}\) und \({\displaystyle \textstyle k>n-k-1}\) kann auch ohne Gaußklammern geschrieben werden:

\({\displaystyle f_{n\geq 1}=\sum _{k=0}^{n-1}{\tbinom {n-k-1}{k}}=\sum _{k=1}^{n}{\tbinom {n-k}{k-1}}}\).

Herleitung  

Die erzeugende Funktion kann auch geschrieben werden:

\({\displaystyle \sum _{n=0}^{\infty }f_{n}z^{n}=0+\sum _{n=1}^{\infty }f_{n}z^{n}={\frac {z}{1-z-z^{2}}};\quad }\)(1)

für dem Betrage nach hinreichend kleine \({\displaystyle z}\) gilt:

\({\displaystyle \sum _{l=1}^{\infty }(z+z^{2})^{l}={\frac {z+z^{2}}{1-(z+z^{2})}}={\frac {z(1+z)}{1-z-z^{2}}}\quad \mid :(1+z)\neq 0}\)

\({\displaystyle \sum _{l=1}^{\infty }z^{l}(1+z)^{l-1}={\frac {z}{1-z-z^{2}}};\quad }\)(2)

Gleichsetzen ergibt:

\({\displaystyle \sum _{n=1}^{\infty }f_{n}z^{n}=\sum _{l=1}^{\infty }z^{l}(1+z)^{l-1}=\sum _{l=1}^{\infty }z^{l}\sum _{k=0}^{l-1}{\tbinom {l-1}{k}}z^{k}=\sum _{n=1}^{\infty }z^{n}\sum _{k=0}^{[{\frac {n-1}{2}}]}{\tbinom {n-k-1}{k}}}\), wobei [] Gaußklammern sind;

bei der Umformung wurden der Binomische Lehrsatz und die Umsummierung \({\displaystyle n=k+l}\) mit \({\displaystyle \textstyle k\leq l-1\Rightarrow k\leq {\frac {n-1}{2}}}\) verwendet.

Koeffizientenvergleich ergibt den angegebenen Zusammenhang.

Die Schreibweise \({\displaystyle G(z)}\) für die erzeugende Funktion erlaubt auch die Darstellung:

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

In der Darstellung von \({\displaystyle G(z)}\) als unendliche Summe ist der Summand mit \({\displaystyle k=0}\) verzichtbar, siehe vorherige Herleitung.

Die \({\displaystyle n}\)-te Ableitung der erzeugenden Funktion ist mit der Potenzregel:

\({\displaystyle {\frac {d^{n}}{dz^{n}}}G(z)=}\)

\({\displaystyle \sum _{k=1}^{\infty }{\frac {d^{n}}{dz^{n}}}f_{k}z^{k}=}\)

\({\displaystyle \sum _{k=1}^{n-1}{\frac {d^{n}}{dz^{n}}}f_{k}z^{k}+{\frac {d^{n}}{dz^{n}}}f_{n}z^{n}+\sum _{k=n+1}^{\infty }{\frac {d^{n}}{dz^{n}}}f_{k}z^{k}=}\)

\({\displaystyle 0+n!f_{n}+\sum _{k=n+1}^{\infty }{\frac {k!}{(k-n)!}}f_{n}z^{k-n};}\)

für \({\displaystyle z=0}\) verschwindet die Summe der letzten Zeile. Für dieses \({\displaystyle z}\) entsteht mit Division durch \({\displaystyle n!\neq 0}\) die Behauptung.

Darstellung mit Matrizen

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

\({\displaystyle {\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 \({\displaystyle A^{m+n}=A^{m}A^{n}}\) ergibt sich beispielsweise die erste oben angegebene Formel für \({\displaystyle f_{m+n}}\). \({\displaystyle 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 \({\displaystyle A^{n}}\) das \({\displaystyle n}\)-te Paar aus dem Startpaar \({\displaystyle (0,1)}\). Dies und die Tatsache, dass die Eigenwerte von \({\displaystyle A}\) gerade der Goldene Schnitt und dessen Kehrwert (letzterer mit negativem Vorzeichen) sind, führen wieder auf die oben genannte Formel von Binet.

Verwandtschaft mit dem Pascalschen Dreieck

Die Fibonacci-Zahlen können mithilfe des Pascalschen Dreiecks beschrieben werden. Um die n-te Fibonacci-Zahl zu bestimmen, nimmt man aus der n-ten Zeile des Pascalschen Dreiecks jede zweite Zahl und gewichtet sie mit der entsprechenden Fünfer-Potenz - anfangend mit 0 in aufsteigender Reihenfolge, d. h. \({\displaystyle 5^{0}}\), \({\displaystyle 5^{1}}\), \({\displaystyle 5^{2}}\), usw. Anschließend addiert man diese gewichteten Elemente zusammen und dividiert durch \({\textstyle 2^{n-1}}\).

Das Bild unten veranschaulicht die Berechnung der ersten sieben Fibonacci-Zahlen aus dem Pascalschen Dreieck. Zum leichteren Verständnis sind die nicht benutzten Elemente des Pascalschen Dreiecks im Bild ausgegraut, die Gewichtung mit den aufsteigenden Fünfer-Potenzen rot und die Exponenten \({\displaystyle 2^{n-1}}\) cyan hervorgehoben.

Herleitung  

Ausgehend von der expliziten Formel für die Fibonacci-Zahlen (s. Formel von Moivre-Binet weiter unten in diesem Artikel)

\({\displaystyle f_{n}={\frac {1}{\sqrt {5}}}\cdot \left(\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}\right),\quad k\geq 0}\)

kann man zunächst den Term \({\displaystyle 2^{n}}\) im Nenner ausklammern und die verbliebene Differenz mittels Binomialkoeffizienten ausschreiben und anschließend zusammenfassen:

\({\displaystyle {\begin{aligned}f_{n}&={\frac {1}{\sqrt {5}}}\cdot {\frac {1}{2^{n}}}\cdot \left(\left(1+{\sqrt {5}}\right)^{n}-\left(1-{\sqrt {5}}\right)^{n}\right)\\&={\frac {1}{\sqrt {5}}}\cdot {\frac {1}{2^{n}}}\cdot \left(\sum _{i=0}^{n}{\binom {n}{i}}1^{n-i}\cdot \left({\sqrt {5}}\right)^{i}-\sum _{i=0}^{n}{\binom {n}{i}}1^{n-i}\cdot \left(-{\sqrt {5}}\right)^{i}\right)\\&={\frac {1}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{i=0}^{n}{\binom {n}{i}}\cdot \left(\left({\sqrt {5}}\right)^{i}-\left(-{\sqrt {5}}\right)^{i}\right)\\\end{aligned}}}\)

Für die Differenz unter dem Summenzeichen gilt:

\({\displaystyle \left({\sqrt {5}}\right)^{i}-\left(-{\sqrt {5}}\right)^{i}={\begin{cases}0\ &{\text{falls }}i\,{\text{gerade}}\\2\cdot \left({\sqrt {5}}\right)^{i}\ &{\text{falls }}i\,{\text{ungerade}}\end{cases}}}\)

so dass man die Summe auf ungerade \({\displaystyle i}\) reduzieren kann:

\({\displaystyle {\begin{aligned}f_{n}&={\frac {1}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot 2\cdot \left({\sqrt {5}}\right)^{2j+1}\\&={\frac {1}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot \left({\sqrt {5}}\right)^{2j}\cdot 2{\sqrt {5}}\\&={\frac {{\sqrt {5}}\cdot 2}{{\sqrt {5}}\cdot 2^{n}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot \left(\left({\sqrt {5}}\right)^{2}\right)^{j}\\&={\frac {1}{2^{n-1}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }{\binom {n}{2j+1}}\cdot 5^{j}.\end{aligned}}}\)

Der \({\displaystyle {\sqrt {5}}}\)-Term kürzt sich also raus und unter dem Summenzeichen bleiben nur Fünfer-Potenzen. Das erklärt das scheinbare Paradoxon, dass die explizite Formel für Fibonacci-Zahlen mit ihren \({\displaystyle {\sqrt {5}}}\)-Termen überhaupt ganze Zahlen liefert. Die Abrundung \({\displaystyle \lfloor n/2\rfloor }\) in der Summen-Obergrenze ist übrigens notwendig, damit die Indizierung nicht über den Wert \({\displaystyle n}\) hinausgeht und die ursprüngliche Summenbegrenzung eingehalten wird.

Vergleicht man die unter dem Summenzeichen verbliebenen Binomialkoeffizienten mit denen im Pascalschen Dreieck, erkennt man das es sich dabei um jeden zweiten Koeffizienten in der entsprechenden Zeile des Dreiecks handelt (wie es im Bild oben visualisiert ist). Man kann die Formel also auch als

\({\displaystyle f_{n}={\frac {1}{2^{n-1}}}\cdot \sum _{j=0}^{\lfloor n/2\rfloor }P_{n,2j+1}\cdot 5^{j}}\)

Mit der Bezeichnung \({\displaystyle P_{n,k}}\) für einen Binomialkoeffizienten an der \({\displaystyle k}\)-ten Stelle in der \({\displaystyle n}\)-ten Zeile des Pascalschen Dreiecks (beide ab Null gezählt!). Als Beispiel erhält man für die 7-te Fibonacci-Zahl etwa den Wert

\({\displaystyle {\begin{aligned}f_{7}&={\frac {1}{2^{6}}}\cdot \sum _{j=0}^{3}P_{7,2j+1}\cdot 5^{j}\\&={\frac {1}{64}}\cdot \left(P_{7,1}\cdot 5^{0}+P_{7,3}\cdot 5^{1}+P_{7,5}\cdot 5^{2}+P_{7,7}\cdot 5^{3}\right)\\&={\frac {1}{64}}\cdot \left(7\cdot 1+35\cdot 5+21\cdot 25+1\cdot 125\right)={\frac {832}{64}}=13.\end{aligned}}}\)

Verallgemeinerungen

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

Jedes dieser Kriterien erlaubt eine Verallgemeinerung:

Für die Glieder einer solchen Folge gilt ein gegenüber der Formel von Moivre-Binet verallgemeinertes explizites Bildungsgesetz:
\({\displaystyle a_{n}\!\,={\frac {k\cdot \Phi ^{n}-l\cdot \Psi ^{n}}{\sqrt {5}}}}\) mit \({\displaystyle k=u\cdot \Psi ^{2}-v\cdot \Psi }\) und \({\displaystyle l=u\cdot \Phi ^{2}-v\cdot \Phi }\).
Die kanonische Folge stellt sich hier als Spezialfall mit \({\displaystyle u=v=1}\) dar, was wegen der charakteristischen Gleichung sofort \({\displaystyle k=1}\) und \({\displaystyle l=1}\) liefert.
\({\displaystyle a_{n}=q\cdot a_{n-2}+p\cdot a_{n-1}}\)
besitzt die charakteristische Gleichung \({\displaystyle x^{2}-px-q=0}\). Die Wurzeln dieser Gleichung bestimmen das explizite Bildungsgesetz. Wenn die charakteristische Gleichung die Wurzeln \({\displaystyle \alpha }\) und \({\displaystyle \beta }\) hat, dann lautet das Bildungsgesetz
\({\displaystyle a_{n}={\frac {k\cdot \alpha ^{n}-l\cdot \beta ^{n}}{\alpha -\beta }},}\)
wobei \({\displaystyle k}\) und \({\displaystyle l}\) wieder durch die Startglieder bestimmt sind.
\({\displaystyle a_{n}=\sum _{i=1}^{n}{k_{i}x_{i}^{n}}}\).
Beispiele für derartige Folgen sind die Tribonacci- und die Tetranacci-Folge.[14][15] Die Perrin-Folge und die Padovan-Folge folgen der Regel \({\displaystyle a_{n}=a_{n-2}+a_{n-3}}\).[16]
Eine Iteration, die nur das unmittelbar vorhergehende Glied verwendet, liefert in diesem Zusammenhang als entartete Fibonacci-Folge eine reine Potenzfolge.

Fibonacci-Folgen in der Natur


Phyllotaxis

Die Blätter (Phyllotaxis) oder Fruchtstände vieler Pflanzen sind in Spiralen angeordnet, wobei die Anzahl dieser Spiralen den Fibonacci-Zahlen entsprechen. In diesem Fall ist der Winkel zwischen architektonisch benachbarten Blättern oder Früchten bezüglich der Pflanzenachse der Goldene Winkel. Das liegt daran, dass Brüche von aufeinanderfolgenden Fibonacci-Zahlen den zugrunde liegenden Goldenen Schnitt am besten approximieren. 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 so die Blätter maximalen Schatten auf darunterliegenden Blättern erzeugen oder maximale ‚Lichtlücken‘ entstehen.

Beispielsweise tragen die Körbe der Silberdistel (Carlina acaulis) hunderte gleichgestaltiger Blüten, die in kleineren Körben in einer 21-zu-55-Stellung, in größeren Körben in 34-zu-89- und 55-zu-144-Stellung in den Korbboden eingefügt sind.[17] 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.[18]

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

Stammbäume

Männchen der Honigbiene (Apis mellifera) werden als Drohnen bezeichnet. Interessanterweise beschreibt die Fibonacci-Folge die Anzahl der Ahnen einer Drohne. Das erklärt sich dadurch, dass eine Drohne (Generation n = 1) sich aus einem unbefruchteten Ei entwickelt, das ausschließlich Erbgut ihrer Mutter, der Bienenkönigin (Generation n = 2), enthält; eine Drohne hat keinen Vater. Eine Königin jedoch hat zwei Eltern, nämlich als Mutter eine andere Königin und als Vater eine Drohne (Generation n = 3) usw. Die Anzahl aller Ahnen einer Drohne in je einer so definierten n-ten Generation ist die n-te Fibonacci-Zahl \({\displaystyle f_{n}}\).

Um das einzusehen, lässt sich die Zeichnung zur Anzahl der Kaninchen in Fibonaccis Modell im Abschnitt "Antike und Mittelalter in Europa" verwenden. Jedes Paar nicht geschlechtsreifer Kaninchen entspricht einer Drohne, jedes Paar geschlechtsreifer Kaninchen einer Königin. In den Gleichungen der Modellierung ist dann \({\displaystyle y_{n}}\) die Anzahl der Drohnen, \({\displaystyle x_{n}}\) die Anzahl der Königinnen (jeweils in der n-ten Generation) und \({\displaystyle f_{n>1}}\) die Anzahl der Ahnen einer Drohne in der betrachteten Generation.

Fettsäuren

Unverzweigte aliphatischen Monocarbonsäuren (hier: uaM), zu denen im Regelfall die Fettsäuren gehören, können verschieden viele Doppelbindungen an verschiedenen Positionen aufweisen. Die Anzahl der uaM gehorcht als Funktion der Kettenlänge der Fibonacci-Folge.[19] Das folgt daraus, dass Doppelbindungen bei uaM nicht benachbart sind; die seltenen Ausnahmen sind hier vernachlässigt. Speziell gibt es nur eine aliphatische Monocarbonsäure mit einem C-Atom: Ameisensäure, eine mit zwei C-Atomen: Essigsäure, zwei mit dreien: Propionsäure und Acrylsäure usw. Bei 18 C-Atomen ergeben sich 2.584 Varianten (wovon Stearinsäure, Ölsäure, Linolsäure und Linolensäure vier Beispiele sind).

Auch hier lässt sich, um das einzusehen, die Zeichnung zur Anzahl der Kaninchen in Fibonaccis Modell im Abschnitt "Antike und Mittelalter in Europa" verwenden. Ein Kaninchenpaar der \({\displaystyle n}\)-ten Generation entspricht dem \({\displaystyle n}\)-ten Kohlenstoffatom einer uaM, wobei die Zählung bei der Carboxygruppe beginnt. Jedes Paar nicht geschlechtsreifer Kaninchen entspricht einem Kohlenstoffatom \({\displaystyle c_{n}}\), auf das keine Doppelbindung folgen kann, jedes Paar geschlechtsreifer Kaninchen einem Kohlenstoffatom \({\displaystyle C_{n}}\), auf das eine Doppelbindung folgen kann (oder nicht). Die Verbindungsstrecken von \({\displaystyle c_{n}}\) nach \({\displaystyle C_{n+1}}\) oder von \({\displaystyle C_{n}}\) nach \({\displaystyle C_{n+1}}\) entsprechen Einfachbindungen, die Verbindungsstrecken von \({\displaystyle C_{n}}\) nach \({\displaystyle c_{n+1}}\) Doppelbindungen. In den Gleichungen der Modellierung ist dann \({\displaystyle y_{n}}\) (bzw. \({\displaystyle x_{n}}\)) die Anzahl der Kohlenstoffatome \({\displaystyle c_{n}}\) (bzw. \({\displaystyle C_{n}}\)). - Jeder Pfad von \({\displaystyle c_{1}}\) zu einem Kohlenstoffatom der \({\displaystyle n}\)-ten Generation entspricht genau einer uaM mit \({\displaystyle n}\) Kohlenstoffatomen; die Zuordnung ist bijektiv. Also ist die Anzahl \({\displaystyle f_{n}}\) der in der \({\displaystyle n}\)-ten Generation betrachteten Kohlenstoffatome gleich der Anzahl der uaM mit \({\displaystyle n}\) Kohlenstoffatomen.

Geschichte


Altes Indien

Ihre früheste Erwähnung findet sich unter dem Namen mātrāmeru („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.).[20] 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.

Antike und Mittelalter in Europa

In der westlichen Welt war diese Folge ebenfalls schon in der Antike Nikomachos von Gerasa (um 100 n. Chr.) bekannt.[21] 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:[22]

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 circumdatus“), sodass kein Tier die Population verlassen und keines von außen hinzukommen kann.

Fibonacci begann die Folge, nicht ganz konsequent, nicht mit einem neugeborenen, sondern mit einem trächtigen Paar, das seinen Nachwuchs bereits im ersten Monat wirft, sodass 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 Folge durch Summierung jeweils zweier aufeinanderfolgender Folgenglieder (2+3 = 5, 3+5 = 8, 5+8 = 13 usw.) hin. Er merkte außerdem an, dass die Folge 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.

Eine 2014 erschienene, mathematisch-historische Analyse zum Leben des Leonardo von Pisa, insbesondere zu seinem Aufenthalt in der nordafrikanischen Hafenstadt Bejaia (im heutigen Algerien), kam zu dem Schluss, dass der Hintergrund der Fibonacci-Folge gar nicht bei einem Modell der Vermehrung von Kaninchen zu suchen ist (was schon länger vermutet wurde), sondern vielmehr bei den Bienenzüchtern von Bejaia und ihrer Kenntnis des Bienenstammbaums zu finden ist. Zu Leonardos Zeit war Bejaia ein wichtiger Exporteur von Bienenwachs, worauf noch heute der französische Name der Stadt (Bougie, wie das frz. Wort für Kerze) hinweist.[23]

Nachdem spätere Mathematiker wie Gabriel Lamé (1795–1870) die Entdeckung dieser Zahlenfolge für sich beansprucht hatten, brachten Édouard Lucas (1842–1891)[24] 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.

Mathematische Modellierung des Wachstums von Fibonaccis Kaninchen-Population

Sei \({\displaystyle x_{n}}\) die Anzahl der geschlechtreifen bzw. \({\displaystyle y_{n}}\) die Anzahl der nicht geschlechtsreifen Kaninchen der \({\displaystyle \textstyle n}\)-ten Generation, entsprechend für die Generationen \({\displaystyle \textstyle n-1}\) und \({\displaystyle \textstyle n-2}\). Nach den oben angegebenen Regeln ist mit diesen Bezeichnungen:

\({\displaystyle x_{n}=x_{n-1}+y_{n-1}}\)   (1);   \({\displaystyle x_{n-1}=x_{n-2}+y_{n-2}}\)  (1');   \({\displaystyle y_{n}=x_{n-1}}\) (2);  

Einsetzen von (1') in (1) und anschließende Addition von (2) ergibt:

\({\displaystyle x_{n}[+y_{n}]=(x_{n-2}+y_{n-2})+y_{n-1}[+x_{n-1}]}\),

für die Gesamtzahl \({\displaystyle f_{n}=x_{n}+y_{n}}\),  \({\displaystyle f_{n-2}=x_{n-2}+y_{n-2}}\),  \({\displaystyle f_{n-1}=x_{n-1}+y_{n-1}}\) von Kaninchen der jeweiligen Generation also

\({\displaystyle f_{n}=f_{n-2}+f_{n-1}}\), was dem angegebenen rekursiven Bildungsgesetz der Fibonacci-Folge äquivalent ist.

Mit \({\displaystyle x_{1}=0,y_{1}=1}\) beschreibt dieses Modell die in der Zeichnung angegebenene Generationenfolge.

Rezeption in Kunst und Unterhaltung


Fibonacci-Datenstrukturen


Die Fibonacci-Folge ist namensgebend für folgende Datenstrukturen, bei deren mathematischer Analyse sie auftritt.

Literatur


Weblinks


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

Einzelnachweise


  1. Folge A000045 in OEIS
  2. Parmanand Singh: The So-called Fibonacci numbers in ancient and medieval India. In: Historia Mathematica. 12, Nr. 3, 1985, S. 229–244. doi:10.1016/0315-0860(85)90021-7 .
  3. a b Ruben Stelzner (in Zusammenarbeit mit Wolfgang Schad): Der Goldene Schnitt. Das Mysterium der Schönheit. In: golden-section.eu. Abgerufen am 26. Oktober 2015.
  4. Obwohl viele der Aussagen weiter unten auch gelten, wenn die Indizes (Subskripte) um einen festen Betrag verschoben werden, hat sich diese Festlegung eingebürgert. Sie hat auch den Vorteil, dass die Ergänzung auf negative Indizes sich symmetrisch zur 0 verhält.
  5. Donald E. Knuth: Negafibonacci Numbers and the Hyperbolic Plane. Annual meeting. Hrsg.: The Mathematical Association of America. The Fairmont Hotel, San Jose, CA 11. Dezember 2008 (allacademic.com ).
  6. Hendrik Lenstra: Profinite Fibonacci numbers. (PDF)
  7. Nicolai N. Vorobiev: Fibonacci Numbers. Birkhäuser, Basel 2002, ISBN 3-7643-6135-2, S. 59 (Online-Version ).
  8. PDF. Bei: sternenreise.com.
  9. Paulo Ribenboim: Meine Zahlen, meine Freunde: Glanzlichter der Zahlentheorie. Springer-Lehrbuch, 2009, ISBN 978-3-540-87955-8, S. 59–62.
  10. Paulo Ribenboim: Meine Zahlen, meine Freunde: Glanzlichter der Zahlentheorie. Springer-Lehrbuch, 2009, ISBN 978-3-540-87955-8, S. 323.
  11. Eric W. Weisstein: Zeckendorf Representation. In: MathWorld (englisch).
  12. In manchen Büchern wird für de Moivres Entdeckung auch 1730 angegeben oder auch die Entdeckung nur Binet zugeschrieben. Für de Moivre, Bernoulli und Binet siehe dazu Beutelspacher (Albrecht Beutelspacher, Bernhard Petri: Der Goldene Schnitt. Spektrum, Heidelberg/Berlin/Oxford 1988, ISBN 3-411-03155-7, S. 90) und Schröder (u. a. in: Herbert Schröder: Wege zur Analysis: Genetisch – Geometrisch – Konstruktiv. Gabler, 2001, ISBN 3-540-42032-0, S. 12 (Auszug (Google) )). Dass die Formel zudem auch Euler bekannt war, findet man z. B. bei Winkler (Peter Winkler: Mehr mathematische Rätsel für Liebhaber. Gabler, 2010, ISBN 978-3-8274-2349-8, S. 46 (Auszug (Google) )) oder Ben-Menahem (Ari Ben-Menahem: Historical Encyclopedia of Natural and Mathematical Sciences. Band 1. Springer, 2009, ISBN 978-3-540-68831-0, S. 611 (Auszug (Google) ))
  13. Gleichung (2.12) in: "Fibonacci numbers and matrices", 15. Juni 2009, Robert C. Johnson, Department of Mathematical Sciences, Durham University, UK
  14. Folge A000073 in OEIS, Folge A000078 in OEIS
  15. Tony Noe, Tito Piezas III und Eric Weisstein: Fibonacci n-Step Number. Wolfram MathWorld, abgerufen am 6. Juli 2017 (englisch).
  16. Folge A001608 in OEIS, Folge A000931 in OEIS
  17. G. Hegi: Illustrierte Flora von Mitteleuropa. Band VI/4. 2. Auflage 1987. Weissdorn Verlag, Jena, ISBN 3-936055-23-8.
  18. Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. World Scientific, Singapur 1999, ISBN 981-02-3264-0, S. 130–134.
  19. S. Schuster, M. Fichtner, S. Sasso: Use of Fibonacci numbers in lipidomics – Enumerating various classes of fatty acids. In: Sci. Rep. 7 (2017) 39821
  20. Parmanand Singh: Acharya Hemachandra and the (so called) Fibonacci Numbers. In: Mathematics Education. 20,1 (Siwan, 1986), ISSN 0047-6269 , S. 28–30.
  21. Friedrich Gustav Lang: Schreiben nach Mass. Zur Stichometrie in der antiken Literatur. In: Novum Testamentum. Vol. 41, Fasc. 1, 1999, S. 40–57. Lang verweist S. 55, Fußnote 86 auf Nikomachos von Gerasa, der diese Reihe neben anderen Zahlenreihen aufgelistet habe.
  22. Baldassare Boncompagni (Hrsg.): Scritti di Leonardo Pisano matematico del secolo decimoterzo. Bd. I, Tipografia delle scienze matematiche e fisiche. Rom 1857, S. 283–284 (Kap. XII, 7: „Quot paria coniculorum in uno anno ex uno pario germinentur“).
  23. T. C. Scott, P. Marketos: On the Origin of the Fibonacci Sequence. Hrsg.: MacTutor History of Mathematics archive, University of St Andrews. 23. März 2014 (englisch, Online bei mcs.st-andrews.ac.uk [PDF; 2,1 MB; abgerufen am 25. September 2018]).
  24. Edouard Lucas: Recherches sur plusieurs ouvrages de Léonard de Pise et sur diverses questions d’arithmétique supérieure. In: Bulletino di bibliografia e di storia delle scienze matematiche e fisiche 10. (1877), S. 129–193, S. 239–293.
  25. Graham Hartmann: „No. 1: Tool, ‘Lateralus’ – Top 21st Century Metal Songs.“ Bei: loudwire.com. Aufgerufen am 22. Februar 2014.
  26. Beitrag in MU – Der Mathematikunterricht „Mathematik und Kunst“. Jg. 55, Heft 2, April 2009. Friedrich Verlag, Herausgeber Stefan Deschauer, TU Dresden, ISSN 0025-5807 .
  27. Ingmar Lehmann: Fibonacci-Zahlen in Bildender Kunst und Literatur. Abgerufen am 7. November 2009 (PDF; 131 kB).
  28. Missing Persons. Bei: watchdogs.wikia.com.
  29. Die Orsons – What’s Goes? Bei: YouTube.com.
  30. Anlage Detailaufnahme 008. Bei: kkl.ch. Abgerufen am 19. Februar 2017.








Kategorien: Folge ganzer Zahlen | Zahlentheorie | Theoretische Biologie | Ganzzahlmenge | Proportionalität








Quelle: Wikipedia - https://de.wikipedia.org/wiki/Fibonacci-Folge (Autoren [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Veränderungen: Alle Bilder und die meisten Designelemente, die mit ihnen in Verbindung stehen, wurden entfernt. Icons wurden teilweise durch FontAwesome-Icons ersetzt. Einige Vorlagen wurden entfernt (wie „Lesenswerter Artikel“, „Exzellenter Artikel“) oder umgeschrieben. CSS-Klassen wurden zum Großteil entfernt oder vereinheitlicht.
Wikipedia spezifische Links, die nicht zu Artikeln oder Kategorien führen (wie „Redlink“, „Bearbeiten-Links“, „Portal-Links“) wurden entfernt. Alle externen Links haben ein zusätzliches FontAwesome Icon erhalten. Neben weiteren kleinen Designanpassungen wurden Media-Container, Karten, Navigationsboxen, gesprochene Versionen & Geo-Mikroformate entfernt.


Stand der Informationen: 02.07.2020 07:00:56 CEST - Wichtiger Hinweis Da die gegebenen Inhalte zum angegebenen Zeitpunkt maschinell von Wikipedia übernommen wurden, war und ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.org nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein oder Fehler in der Darstellung vorliegen, bitten wir Sie darum uns per zu kontaktieren: E-Mail.
Beachten Sie auch : Impressum & Datenschutzerklärung.