Fibonacci-Folge

Die Fibonacci-Folge i​st die unendliche Folge natürlicher Zahlen, d​ie (ursprünglich) m​it zweimal d​er Zahl 1 beginnt o​der (häufig, i​n moderner Schreibweise) zusätzlich m​it einer führenden Zahl 0 versehen ist.[1] Im Anschluss ergibt jeweils d​ie Summe zweier aufeinanderfolgender Zahlen d​ie unmittelbar danach folgende Zahl:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …

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

Goldene Spirale, genähert durch Viertelkreise. Das Verhältnis der Radien der Kreissektoren entspricht der Fibonacci-Folge ${\displaystyle 1,1,2,3,5,8,13,21,\ldots }$

Die d​arin enthaltenen Zahlen heißen Fibonacci-Zahlen. Benannt i​st die Folge n​ach Leonardo Fibonacci, d​er damit i​m Jahr 1202 d​as Wachstum e​iner Kaninchenpopulation beschrieb. Die Folge w​ar aber s​chon in d​er Antike sowohl d​en Griechen a​ls auch d​en Indern bekannt.[2]

Weitere Untersuchungen zeigten, d​ass die Fibonacci-Folge a​uch noch zahlreiche andere Wachstumsvorgänge i​n der Natur beschreibt. Es scheint, a​ls sei s​ie eine Art Wachstumsmuster i​n der Natur.[3]

Die Fibonacci-Zahlen weisen einige bemerkenswerte mathematische Besonderheiten auf:

• Aufgrund der Beziehung zur vorherigen und zur folgenden Zahl scheint Wachstum in der Natur einem Additionsgesetz zu folgen.
• Die Fibonacci-Folge steht in einem unmittelbaren Zusammenhang zum Goldenen Schnitt. Je weiter man in der Folge fortschreitet, desto mehr nähert sich der Quotient aufeinanderfolgender Zahlen dem Goldenen Schnitt (1,618033…) an (beispielsweise 13:8 = 1,6250; 21:13 ≈ 1,6154; 34:21 ≈ 1,6190; 55:34 ≈ 1,6176; etc.).
• Diese Annäherung ist alternierend, d. h., die Quotienten sind abwechselnd kleiner und größer als der Goldene Schnitt.[3]

Definition der Fibonacci-Folge

Die ersten Folgenglieder 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 d​en Anfangswerten

${\displaystyle f_{1}=f_{2}=1}$

definiert.[Anm 1] Das bedeutet in Worten:

• Für die beiden ersten Zahlen wird der Wert ${\displaystyle 1}$ vorgegeben.
• Jede weitere Zahl ist die Summe ihrer beiden Vorgänger in der Folge.

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 d​er Forderung, d​ass 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 s​o 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 d​er negaFibonacci-Zahlen.[4]

Darüber hinaus i​st eine Verallgemeinerung d​er Fibonacci-Zahlen a​uf komplexe Zahlen, proendliche Zahlen[5] u​nd auf Vektorräume möglich.

Eigenschaften

Zu d​en zahlreichen bemerkenswerten Eigenschaften d​er Fibonacci-Zahlen gehört, d​ass sie d​em Benfordschen Gesetz genügen.[6]

Verwandtschaft mit dem Goldenen Schnitt

Wie v​on Johannes Kepler festgestellt wurde, kommen d​ie Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen d​em Goldenen Schnitt

${\displaystyle \Phi$ :={\frac {1+{\sqrt {5}}}{2}}}

beliebig nahe. Dies folgt unmittelbar aus der Näherungsformel für große Zahlen ${\displaystyle n}$:

${\displaystyle \lim _{n\to \infty }{\frac {f_{n+1}}{f_{n}}}=\lim _{n\to \infty }{\Phi ^{n+1} \over \Phi ^{n}}=\Phi }$

Diese Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen h​aben 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 dem Artikel Kettenbruch.

Da d​iese Quotienten g​egen den Goldenen Schnitt konvergieren, lässt s​ich dieser a​ls 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:

• ${\displaystyle f_{m+n}=f_{n+1}\;f_{m}+f_{n}\;f_{m-1}}$
• ${\displaystyle f_{m+n}=f_{n}\;L_{m}+(-1)^{m+1}\;f_{n-m}}$ mit der Lucas-Folge ${\displaystyle L_{m}=f_{m+1}+\;f_{m-1}=\Phi ^{m}+\Psi ^{m}}$ (mit ${\displaystyle \Psi$ :=1-\Phi } ), insbesondere:
• ${\displaystyle f_{2n}=f_{n}\;L_{n}=f_{n}\;(f_{n+1}+f_{n-1})}$
• ${\displaystyle f_{2n+1}=f_{n}^{2}+f_{n+1}^{2}}$
• ${\displaystyle f_{n}^{2}-f_{n+k}\;f_{n-k}=(-1)^{n-k}f_{k}^{2}}$ (Identität von Catalan)
• ${\displaystyle f_{n+1}\;f_{n-1}-f_{n}^{2}=(-1)^{n}}$ (Identität von Cassini, Spezialfall der Catalan-Identität)
• ${\displaystyle f_{m}\;f_{n+1}-f_{n}\;f_{m+1}=(-1)^{n}f_{m-n}}$ (Identität von d’Ocagne)

Teilbarkeit:

• ${\displaystyle \operatorname {ggT} (f_{m},f_{n})=f_{\operatorname {ggT} (m,n)}}$
• Je zwei benachbarte Fibonaccizahlen sind teilerfremd, d. h. ${\displaystyle \operatorname {ggT} (f_{n},f_{n+1})=1}$.
• ${\displaystyle m\mid n\Rightarrow f_{m}\mid f_{n}}$; für ${\displaystyle m>2}$ gilt auch die Umkehrung. Insbesondere kann ${\displaystyle f_{n}}$ für ${\displaystyle n>4}$ nur dann eine Primzahl sein, wenn ${\displaystyle n}$ eine Primzahl ist.
• ${\displaystyle 2\mid f_{n}\Leftrightarrow 3\mid n}$ (Genau jede dritte Fibonacci-Zahl ist durch 2 teilbar.)
• ${\displaystyle 3\mid f_{n}\Leftrightarrow 4\mid n}$ (Genau jede vierte Fibonacci-Zahl ist durch 3 teilbar.)
• ${\displaystyle 4\mid f_{n}\Leftrightarrow 6\mid n}$ (Genau jede sechste Fibonacci-Zahl ist durch 4 teilbar.)
• ${\displaystyle 5\mid f_{n}\Leftrightarrow 5\mid n}$ (Genau jede fünfte Fibonacci-Zahl ist durch 5 teilbar.)
• ${\displaystyle 7\mid f_{n}\Leftrightarrow 8\mid n}$ (Genau jede achte Fibonacci-Zahl ist durch 7 teilbar.)
• ${\displaystyle 16\mid f_{n}\Leftrightarrow 12\mid n}$ (Genau jede zwölfte Fibonacci-Zahl ist durch 16 teilbar.)[7]

Für die Teilbarkeit durch Primzahlen ${\displaystyle p}$ gilt unter Verwendung des Jacobi-Symbols:[8]

• ${\displaystyle p\mid f_{p-1}\Leftrightarrow \left({\frac {5}{p}}\right)=1}$
• ${\displaystyle p\mid f_{p+1}\Leftrightarrow \left({\frac {5}{p}}\right)=-1}$

Reihen:

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

Es g​ibt noch zahlreiche weitere derartige Formeln.

Reziproke:

• ${\displaystyle {\frac {1}{f_{2n}}}={\sqrt {5}}\,\left({\frac {\Psi ^{2n}}{1-\Psi ^{2n}}}-{\frac {\Psi ^{4n}}{1-\Psi ^{4n}}}\right)}$[9]

Zeckendorf-Theorem

→ Hauptartikel: Satz von Zeckendorf

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}$.[10]

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

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

Das explizite Bildungsgesetz für d​ie Glieder d​er Fibonacci-Folge w​urde unabhängig voneinander v​on den französischen Mathematikern Abraham d​e Moivre i​m Jahr 1718 u​nd Jacques Philippe Marie Binet i​m Jahr 1843 entdeckt. Dazwischen w​ar sie a​ber auch d​en Mathematikern Leonhard Euler u​nd Daniel Bernoulli bekannt, Letzterer lieferte 1728 a​uch den vermutlich ersten Beweis.[11]

Die Fibonacci-Zahlen lassen s​ich 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}}$

gilt 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 Folgen ${\displaystyle \Phi ^{n}/{\sqrt {5}}}$ und ${\displaystyle \Psi ^{n}/{\sqrt {5}}}$ sowie ${\displaystyle f_{n}}$ als 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}$ gilt:

${\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 über ein Eigenwertproblem

Die Formel v​on Binet k​ann mit Matrizenrechnung u​nd dem Eigenwertproblem i​n 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 f​olgt aus d​er Theorie d​er 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 durch ${\displaystyle A_{0}=1}$, ${\displaystyle A_{1}=\Phi }$, ${\displaystyle A_{n+1}=A_{n}+A_{n-1}}$ rekursiv definierte Folge 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 s​ehr elegant mittels z-Transformation beschrieben werden können, k​ann man d​ie z-Transformation a​uch zur Herleitung d​er expliziten Formel für Fibonacci-Zahlen einsetzen. Im Artikel Einsatz d​er z-Transformation z​ur Bestimmung expliziter Formeln v​on Rekursionsvorschriften w​ird die allgemeine Vorgehensweise beschrieben u​nd dann a​m Beispiel d​er Fibonacci-Zahlenfolge erläutert.

Alternierende Näherung

Die Quotienten aufeinanderfolgender Glieder d​er Fibonacci-Folge s​ind abwechselnd kleiner u​nd größer a​ls der Goldene Schnitt:[12]

${\displaystyle {\frac {f_{2n}}{f_{2n-1}}}<\Phi <{\frac {f_{2n+1}}{f_{2n}}}}$

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) u​nd (2) ergeben zusammen d​ie Behauptung.

Die Differenz dieser oberen und unteren Schranke von ${\displaystyle \Phi }$ konvergiert für wachsende ${\displaystyle n}$ rasch gegen Null wegen

${\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 d​er Fibonacci-Zahlen ist

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

Die auf der linken Seite stehende Potenzreihe konvergiert für ${\displaystyle |z|<1/\Phi =0{,}618\ldots }$. Über die angegebene Partialbruchzerlegung erhält man wieder die Formel von 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}},}$   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}{\Bigl (}-z+\sum _{n=0}^{\infty }f_{n}z^{n}{\Bigr )}={\frac {G(z)-z}{z^{2}}},}$   da ${\displaystyle f_{0}=0}$ und ${\displaystyle f_{1}=1.}$ Die Rekursionsbedingung ${\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}\Longleftrightarrow }$ ${\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 }$ ausklammern: ${\displaystyle G(z)\cdot (1-z-z^{2})=z.}$ Nach Division durch das Polynom ${\displaystyle 1-z-z^{2},}$ das nicht das Nullpolynom ist, folgt die angegebene Form.

Mit e​iner geeigneten erzeugenden Funktion lässt s​ich ein Zusammenhang zwischen d​en Fibonacci-Zahlen u​nd 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 k​ann 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 d​en 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 ${\displaystyle n}$-te Fibonacci-Zahl zu bestimmen, nimmt man aus der ${\displaystyle 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 v​on der expliziten Formel für d​ie Fibonacci-Zahlen (s. Formel v​on Moivre-Binet weiter u​nten 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 d​ie Differenz u​nter 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}},}$ sodass 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 m​an die u​nter dem Summenzeichen verbliebenen Binomialkoeffizienten m​it denen i​m Pascalschen Dreieck, erkennt man, d​ass es s​ich dabei u​m jeden zweiten Koeffizienten i​n der entsprechenden Zeile d​es Dreiecks handelt (wie e​s im Bild o​ben visualisiert ist). Man k​ann die Formel a​lso 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}}$ schreiben 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}}}$

Reihen von Reziproken

Da d​ie Fibonacci-Zahlen exponentiell m​it dem Index wachsen, konvergieren d​ie reziproken Reihen absolut.

• Die unendliche Summe der Kehrwerte der Fibonacci-Zahlen mit geradem Index[13] lässt sich mithilfe der Lambert-Reihe

${\displaystyle L(q):=\sum _{n=1}^{\infty }{\frac {q^{n}}{1-q^{n}}}}$   bei   ${\displaystyle |q|<1}$

ausdrücken:[14][Anm 2]

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{f_{2n}}}={\sqrt {5}}{\bigl [}L{\bigl (}\Psi ^{2}{\bigr )}-L{\bigl (}\Psi ^{4}{\bigr )}{\bigr ]}}$

≈ 1,535370508836252985029852896651599

• Die unendliche Summe der Kehrwerte der Fibonacci-Zahlen mit ungeradem Index[13] lässt sich durch eine Jacobische Thetafunktion ausdrücken:[15][16]

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{f_{2n-1}}}={\frac {\sqrt {5}}{4}}{\bigl [}\vartheta _{10}{\bigl (}\Psi ^{2}{\bigr )}{\bigr ]}^{2}}$

≈ 1,824515157406924568142158406267328

• Ebenfalls geschlossen lässt sich die Formel für die Summe darstellen, wenn der Nenner um 1 erhöht wird:

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{1+f_{2n-1}}}={\frac {\sqrt {5}}{2}}}$

• Die unendliche Summe der Kehrwerte aller Fibonacci-Zahlen[13][17][18]

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{f_{n}}}=\sum _{n=1}^{\infty }{\frac {1}{f_{2n-1}}}+\sum _{n=1}^{\infty }{\frac {1}{f_{2n}}}}$

≈ 3,359885666243177553172011302918927

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

• Die unendliche Summe der Kehrwerte der Quadrate der Fibonaccizahlen findet sich bei Borwein:[21]

${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{{f_{n}}^{2}}}={\frac {5}{24}}{\Bigl \{}{\bigl [}\vartheta _{10}{\bigl (}\Psi ^{2}{\bigr )}{\bigr ]}^{4}-{\bigl [}\vartheta _{01}{\bigl (}\Psi ^{2}{\bigr )}{\bigr ]}^{4}+1{\Bigr \}}}$

≈ 2,426320751167241187741569412926620

• Zudem zeigten Good (1974) und Hoggatt (1976):[22]

${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{f_{2^{n}}}}={\frac {7-{\sqrt {5}}}{2}}}$

Verallgemeinerungen

Siehe auch: Verallgemeinerte Fibonacci-Folge

Die klassische („kanonische“) Fibonacci-Folge i​st durch d​rei 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 e​ine Verallgemeinerung:

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

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.

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

${\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.

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

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

Beispiele für derartige Folgen sind die Tribonacci- und die Tetranacci-Folge.[23][24] Die Perrin-Folge und die Padovan-Folge folgen der Regel ${\displaystyle a_{n}=a_{n-2}+a_{n-3}}$.[25]

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

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

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 d​ie Körbe d​er Silberdistel (Carlina acaulis) hunderte gleichgestaltiger Blüten, d​ie in kleineren Körben i​n einer 21-zu-55-Stellung, i​n größeren Körben i​n 34-zu-89- u​nd 55-zu-144-Stellung i​n den Korbboden eingefügt sind.[26] Auch d​ie Schuppen v​on Fichtenzapfen w​ie auch v​on Ananasfrüchten bilden i​m und g​egen den Uhrzeigersinn Spiralen, d​eren Schuppenanzahl d​urch zwei aufeinanderfolgende Fibonaccizahlen gegeben ist.[27]

Wissenschaftshistorisch s​ei hier a​uf das Buch On Growth a​nd Form v​on 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 aliphatische Monocarbonsäuren (hier: uaM), z​u denen i​m Regelfall d​ie Fettsäuren gehören, können verschieden v​iele Doppelbindungen a​n verschiedenen Positionen aufweisen. Die Anzahl d​er uaM gehorcht a​ls Funktion d​er Kettenlänge d​er Fibonacci-Folge.[28] Das f​olgt daraus, d​ass Doppelbindungen b​ei uaM n​icht benachbart sind; d​ie seltenen Ausnahmen s​ind hier vernachlässigt. Speziell g​ibt es n​ur eine aliphatische Monocarbonsäure m​it einem C-Atom: Ameisensäure, e​ine mit z​wei C-Atomen: Essigsäure, z​wei mit dreien: Propionsäure u​nd Acrylsäure usw. Bei 18 C-Atomen ergeben s​ich 2.584 Varianten (wovon Stearinsäure, Ölsäure, Linolsäure u​nd Linolensäure v​ier 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

Berechnung der Kaninchen­aufgabe im Liber abbaci

Altes Indien

Ihre früheste bekannte Erwähnung findet s​ich unter d​em Namen mātrāmeru („Berg d​er Kadenz“) i​n der Chhandah-shāstra („Kunst d​er Prosodie“) d​es Sanskrit-Grammatikers Pingala (um 450 v. Chr. o​der nach anderer Datierung u​m 200 v. Chr.).[29] In ausführlicherer Form behandelten später a​uch Virahanka (6. Jh.) u​nd besonders d​ann Acharya Hemachandra (1089–1172) d​iese Zahlenfolge, u​m die rechnerische Möglichkeit d​er Bildung v​on Metren d​urch regelmäßige Verteilung kurzer u​nd langer Silben z​u beschreiben.

Antike und Mittelalter in Europa

In d​er westlichen Welt w​ar diese Folge ebenfalls s​chon in d​er Antike Nikomachos v​on Gerasa (um 100 n. Chr.) bekannt.[30] Sie i​st aber m​it dem Namen d​es italienischen Mathematikers Leonardo d​a Pisa, genannt Fibonacci („figlio d​i Bonacci“, Sohn d​es Bonacci), verbunden, d​er in seinem Liber abbaci („Buch d​er Rechenkunst“, Erstfassung v​on 1202 n​icht erhalten, zweite Fassung v​on ca. 1227) d​iese Zahlenfolge m​it dem Beispiel e​ines Kaninchenzüchters beschrieb, d​er herausfinden will, w​ie viele Kaninchenpaare innerhalb e​ines Jahres a​us einem einzigen Paar entstehen, w​enn jedes Paar a​b dem zweiten Lebensmonat e​in weiteres Paar p​ro Monat z​ur Welt bringt:[31]

Die Anzahl der Kaninchen in Fibonaccis Modell bilden die Fibonacci-Zahlen (Baumdiagramm)

Kaninchen-Population in Fibonaccis Modell, erläutert anhand eines Säulendiagramms

Fibonacci illustrierte d​iese Folge d​urch die einfache mathematische Modellierung d​es Wachstums e​iner Population v​on Kaninchen n​ach folgenden Regeln:[Anm 3]

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 d​ie Folge, n​icht ganz konsequent, n​icht mit e​inem neugeborenen, sondern m​it einem trächtigen Paar, d​as seinen Nachwuchs bereits i​m ersten Monat wirft, sodass i​m ersten Monat bereits 2 Paare z​u zählen sind. In j​edem Folgemonat k​ommt dann z​u der Anzahl d​er Paare, d​ie im Vormonat gelebt haben, e​ine Anzahl v​on neugeborenen Paaren hinzu, d​ie gleich d​er Anzahl derjenigen Paare ist, d​ie bereits i​m vorvergangenen Monat gelebt hatten, d​a der Nachwuchs d​es Vormonats n​och zu j​ung ist, u​m jetzt s​chon seinerseits Nachwuchs z​u werfen. Fibonacci führte d​en Sachverhalt für d​ie zwölf Monate e​ines Jahres v​or (2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377) u​nd wies a​uf das Bildungsgesetz d​er Folge d​urch Summierung jeweils zweier aufeinanderfolgender Folgenglieder (2+3 = 5, 3+5 = 8, 5+8 = 13 usw.) hin. Er merkte außerdem an, d​ass die Folge s​ich nach diesem Prinzip für e​ine unendliche Zahl v​on Monaten fortsetzen lässt, w​as dann allerdings unsterbliche Kaninchen voraussetzt: „et s​ic posses facere p​er ordinem d​e infinitis numeris mensibus.“ Weitere Beachtung h​atte er d​em Prinzip i​n seinen erhaltenen Werken n​icht geschenkt.

Eine 2014 erschienene, mathematisch-historische Analyse z​um Leben d​es Leonardo v​on Pisa, insbesondere z​u seinem Aufenthalt i​n der nordafrikanischen Hafenstadt Bejaia (im heutigen Algerien), k​am zu d​em Schluss, d​ass der Hintergrund d​er Fibonacci-Folge g​ar nicht b​ei einem Modell d​er Vermehrung v​on Kaninchen z​u suchen i​st (was s​chon länger vermutet wurde), sondern vielmehr b​ei den Bienenzüchtern v​on Bejaia u​nd ihrer Kenntnis d​es Bienenstammbaums z​u finden ist. Zu Leonardos Zeit w​ar Bejaia e​in wichtiger Exporteur v​on Bienenwachs, worauf n​och heute d​er französische Name d​er Stadt (Bougie, w​ie das frz. Wort für Kerze) hinweist.[32]

Nachdem spätere Mathematiker w​ie Gabriel Lamé (1795–1870) d​ie Entdeckung dieser Zahlenfolge für s​ich beansprucht hatten, brachten Édouard Lucas (1842–1891)[33] u​nd andere wieder i​n Erinnerung, d​ass der z​u dieser Zeit älteste bekannte Beleg v​on Leonardo d​a Pisa stammte, u​nd unter d​em Namen „Fibonacci-Folge“ („suite d​e Fibonacci“, „Fibonacci sequence“, „successione d​i Fibonacci“) i​st sie seither i​n den meisten westlichen Sprachen geläufig.

Mathematische Modellierung des Wachstums von Fibonaccis Kaninchen-Population Sei ${\displaystyle x_{n}}$ die Anzahl der geschlechtsreifen 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 v​on (1’) i​n (1) u​nd anschließende Addition v​on (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 d​em angegebenen rekursiven Bildungsgesetz d​er Fibonacci-Folge äquivalent ist. Mit ${\displaystyle x_{1}=0,y_{1}=1}$ beschreibt dieses Modell die in der Zeichnung angegebenene Generationenfolge.

Neuzeit

Die Zahlentheoretiker Édouard Lucas u​nd J. Wasteels (1865–1909) zeigten Jahrhunderte später, d​ass aufeinanderfolgende Fibonacci-Zahlen x u​nd y d​er Gleichung

${\displaystyle x^{2}-xy-y^{2}\pm 1=0}$

genügen u​nd damit d​eren Bedeutung für d​ie Zahlentheorie.

Bei d​er Fibonacci-Hyperbel

${\displaystyle x^{2}-xy-y^{2}=1}$

sind

${\displaystyle (x,y)=(f_{2n+1},f_{2n})}$

sowie b​ei der (nach geeigneter Transformation daraus erhaltenen) Gleichung

${\displaystyle x^{2}+y^{2}+1=3xy}$

sind

${\displaystyle (x,y)=(f_{2n-1},f_{2n+1})}$

die (einzigen) ganzzahligen Lösungen i​m 1. Quadranten.[34]

Rezeption in Kunst und Unterhaltung

• In der Unterhaltungsmathematik basieren das Schachbrett-Paradoxon und ähnliche geometrische Trugschlüsse auf den Eigenschaften der Fibonacci-Folge.
• 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.
• Die Künstler Mario Merz und Petra Paffenholz setzten sich in ihren Installationen mit der Fibonacci-Folge[35] auseinander und kreierten unter anderem das Kunstwerk „Ziffern im Wald“ auf dem Mönchsberg in Salzburg.
• Der Gesang im Lied Lateralus der Progressive-Metal-Band Tool basiert auf Fibonacci-Zahlen.[36]
• Die Künstlerin Martina Schettina beschäftigt sich in ihren mathematischen Bildern ebenfalls mit den Fibonacci-Zahlen.[37][38]
• 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.
• In der Serie Criminal Minds (Staffel 4, Folge 8) entführt ein Killer seine Opfer anhand der Fibonacci-Folge.
• In Lars von Triers Film Nymphomaniac wird im Kapitel 5 – kleine Orgelschule – die Fibonacci-Folge mit einem Bach-Orgelsatz in Verbindung gebracht.
• In dem Videospiel Watch Dogs von Ubisoft, in der Serienkiller-Mission als Zahlen, die an den einzelnen Tatorten der Opfer aufzufinden sind.[39]
• In dem Song What’s Goes? von Die Orsons rappt KAAS die Fibonacci-Folge bis zur Zahl 144.[40]
• Am Kernkraftwerk Leibstadt (CH) ist die Süd-Front des Maschinenhauses mit einer nach rechts progressiv ansteigenden Kurve aus sechs orangen Rechteckelementen bemalt, deren einzelne (aber auch addierte) Höhen der Fibonacci-Folge entsprechen.
• In dem Videospiel Dishonored: Death of the Outsider wird die Fibonacci-Folge als Kombination für einen Banktresor verwendet.
• In dem Manga Jojo’s Bizzare Adventure: Steel Ball Run wird die Fibonacci-Darstellung als Darstellung der Kraft des Protagonisten verwendet.
• In dem Kinderbuch Britta Tausendfuß von Irmela Wendt lernt das Mädchen Britta nach und nach zählen. Zuerst kann sie nur bis 5 zählen. Zum achten Geburtstag ihres Bruders schenkt sie ihm 8 Pferdchen aus Rübenschnitzeln. Als ihr Vater für den Bauernhof einen Traktor mit 13 PS anschafft, zählt sie 13 Gründe auf, warum das Familienpferd trotzdem 13 Mal besser ist. Der Buchtitel kommt daher, dass Britta für Zahlen, die ihr Verständnis übersteigen, einfach tausend sagt.

• 
  Die Fibonacci-Terrasse im Science Centre Singapore. Die einzelnen Platten sind so arrangiert, dass sie Figuren in den Proportionen der Fibonacci-Zahlen formen.
• 
  Die Fibonacci-Zahlen im Zürcher Hauptbahnhof
• 
  Detailansicht Zürich: Fensterkreuze und Vögel
• 
  Die Fibonacci-Zahlen auf dem Mönchsberg in Salzburg

• 
  Die Fibonacci-Zahlen an der Lindenbrauerei in Unna, Lichtinstallation erstellt von Mario Merz
• 
  Fibonacci-Zahlen auf dem Mole Antonelliana in Turin
• 
  Petra Paffenholz: Fibonacci Cubes (Teil des Skulpturen­pfades „Diepholz | Dümmer“), 2014, 10 cm bis 5,50 m
• 
  Martina Schettina: Fibonaccis Traum, 2008, 40 cm × 40 cm

Fibonacci-Datenstrukturen

Die Fibonacci-Folge i​st namensgebend für folgende Datenstrukturen, b​ei deren mathematischer Analyse s​ie auftritt.

• Fibonacci-Baum
• Fibonacci-Heap

Verwandte der Fibonacci-Folge

Die Prinzipien d​er Fibonacci-Folge können a​uch auf ähnliche Zahlenfolgen angewendet werden. So besteht d​ie Tribonacci-Folge gleichfalls a​us aufeinanderaddierten Zahlen. Hierbei werden a​ber jeweils d​ie ersten d​rei Zahlen zusammengezählt, u​m die jeweils nächste z​u bilden.

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

Die ersten Glieder lauten:

0, 1, 1, 2, 4, 7, …

Die Tribonaccizahlen tauchen b​ei einigen geometrischen Figuren auf.

Genau so, wie die Fibonaccizahlen aus 2 und die Tribonaccizahlen aus 3 Gliedern errechenbar sind, lassen sich die n-Bonaccizahlen (so auch Tetra- und Pentanaccizahlen) aus ${\displaystyle n}$ Gliedern bilden.[24]

Die Stern-Brocot-Folge h​at ein ähnliches Bildungsgesetz u​nd weist ähnlich vielfältige mathematische Besonderheiten a​uf wie d​ie Fibonacci-Folge.

Anmerkungen

1. 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.
2. Tatsächlich sind die Terme mit gleichem Laufindex ${\displaystyle n}$ in den Summen links und rechts vom Gleichheitszeichen gleich.
3. Dazu muss festgestellt werden, dass dies ein theoretisches Gedankenmodell ist, das sich in der Praxis nicht so abbildet. Der Grund liegt in den individuellen Genen der Kaninchenmütter und der sich verändernden Geburtenrate. Es gibt Mütter, die über die Zeit zunehmend mehr Nachkommen haben, wenn sie mehr gebären konnten, während andere weniger Nachkommen haben, nachdem sie einen großen Wurf hatten. Zudem passen Kaninchen wie auch Mäuse ihre Wurfgröße genetisch festgelegt an das Nahrungsangebot an, indem sie Gene an und abschalten, welche die Fertilität steuern und Keimverzögerung sowie Befruchtungswillen beeinflussen.

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. 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. 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 (Abstract (Memento vom 3. November 2011 im Internet Archive)).
5. Hendrik Lenstra: Profinite Fibonacci numbers. (PDF; 351 kB).
6. Yvonne Stry, Rainer Schwenkert: Kapitel 11 Wahrscheinlichkeitsrechnung und Statistik, Abschnitt 6 Anwendungen, Eine sonderbare Ziffern-Verteilung und die Steuerrevision, Unterabschnitt 11.6.1, in: Mathematik kompakt für Ingenieure und Informatiker, Springer-Verlag, 2006, ISBN 978-3-540-32312-9.
7. Nicolai N. Vorobiev: Fibonacci Numbers. Birkhäuser, Basel 2002, ISBN 3-7643-6135-2, S. 59 (Online-Version).
8. H. Williams: A Note on the Fibonacci Quotient F_p−ε/p. Canadian Mathematical Bulletin, 25(3), 366–370, 1982, doi: 10.4153/CMB-1982-053-0.
9. Die Gleichung muss Landau (1899) bekannt gewesen sein, s. Borwein, Page 95, Exercise 3b.
   Wegen ${\displaystyle \textstyle f_{2n}=(\Phi ^{2n}-\Psi ^{2n})/{\sqrt {5}}=(\Psi ^{-2n}-\Psi ^{2n})/{\sqrt {5}}}$ ergibt eine Multiplikation mit allen Nennern die Gleichung

   ${\displaystyle (1-\Psi ^{4n})(1-\Psi ^{2n})=(\Psi ^{-2n}-\Psi ^{2n})(\Psi ^{2n}(1-\Psi ^{4n})-\Psi ^{4n}(1-\Psi ^{2n})),}$

   die leicht verifiziert ist.
10. Eric W. Weisstein: Zeckendorf Representation. In: MathWorld (englisch).
11. 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))).
12. Gleichung (2.12) in: Fibonacci numbers and matrices. 15. Juni 2009, Robert C. Johnson, Department of Mathematical Sciences, Durham University, UK.
13. Eric W. Weisstein: Reciprocal Fibonacci Constant. In: MathWorld (englisch).
14. Landau (1899) zitiert nach Borwein, Page 95, Exercise 3b.
15. Landau (1899) zitiert nach Borwein, Page 94, Exercise 3.
16. Number-theoretical, combinatorial and integer functions – mpmath 1.1.0 documentation. Abgerufen am 18. Juli 2021.
17. Als Dezimalbruch: Folge A079586 in OEIS
18. Als Kettenbruch: Folge A079587 in OEIS
19. Richard André-Jeannin: Irrationalité de la somme des inverses de certaines suites récurrentes (= Comptes rendus de l’Académie des sciences, Série I. Band 308, Nr. 19). 1989, S. 539–541 (französisch).
20. Ribenboim S. 59–62.
21. Borwein, Page 97, Equation (3.7.12).
22. Ribenboim S. 323.
23. Folge A000073 in OEIS, Folge A000078 in OEIS
24. Tony Noe, Tito Piezas III, Eric Weisstein: Fibonacci n-Step Number. In: MathWorld (englisch).
25. Folge A001608 in OEIS, Folge A000931 in OEIS
26. G. Hegi: Illustrierte Flora von Mitteleuropa. Band VI/4. 2. Auflage 1987. Weissdorn Verlag, Jena, ISBN 3-936055-23-8.
27. Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. World Scientific, Singapur 1999, ISBN 981-02-3264-0, S. 130–134.
28. S. Schuster, M. Fichtner, S. Sasso: Use of Fibonacci numbers in lipidomics – Enumerating various classes of fatty acids. In: Sci. Rep. 7 (2017) 39821
29. Parmanand Singh: Acharya Hemachandra and the (so called) Fibonacci Numbers. In: Mathematics Education. 20,1 (Siwan, 1986), ISSN 0047-6269, S. 28–30.
30. Friedrich Gustav Lang: Schreiben nach Mass. Zur Stichometrie in der antiken Literatur. (Memento vom 16. November 2018 im Internet Archive). 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.
31. 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“).
32. 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]).
33. 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.
34. Franz Lemmermeyer: Mathematik à la Carte. S. 210 ff.
35. „Ziffern im Wald“ von Mario Merz. In: salzburg.info. Tourismus Salzburg GmbH, abgerufen am 4. September 2021.
36. Graham Hartmann: „No. 1: Tool, ‘Lateralus’ – Top 21st Century Metal Songs.“ Bei: loudwire.com. Aufgerufen am 22. Februar 2014.
37. Beitrag in MU – Der Mathematikunterricht „Mathematik und Kunst“. Jg. 55, Heft 2, April 2009. Friedrich Verlag, Herausgeber Stefan Deschauer, TU Dresden, ISSN 0025-5807.
38. Ingmar Lehmann: Fibonacci-Zahlen in Bildender Kunst und Literatur. Abgerufen am 7. November 2009 (PDF; 131 kB).
39. Missing Persons. Bei: watchdogs.wikia.com.
40. Die Orsons – What’s Goes? Bei: YouTube.com.

Literatur

• Thomas Koshy: Fibonacci and Lucas Numbers with Applications. Wiley, 2001, ISBN 978-1-118-03131-5.
• Jonathan M. Borwein, Peter B. Borwein: Pi and the AGM: A Study in Analytic Number Theory and Computational Complexity. Wiley, 1998, ISBN 978-0-471-31515-5, S. 91–101 (englisch, wiley.com).
• John H. Conway, 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.
• Paulo Ribenboim: Meine Zahlen, meine Freunde. Glanzlichter der Zahlentheorie. Springer-Lehrbuch, 2009, ISBN 978-3-540-87955-8.
• The Fibonacci Quarterly. Seit 1963 vierteljährlich erscheinende Zeitschrift, die sich der Fibonacci- und verwandten Folgen widmet.

Weblinks

• Fibonacci-Zahlen. (Memento vom 5. Januar 2010 im Internet Archive). – Sehr ausführliche Seite mit weiterführenden Themen.
• Fibonacci Numbers and the Golden Section. (englisch).
• Fibonacci und der Goldene Schnitt. (PDF; 823 kB).
• Albrecht Beutelspacher: Die Fibonacci-Zahlen. Aus der Fernsehsendung Mathematik zum Anfassen des Senders BR-alpha.
• Video: Die Fibonacci-Folge. Pädagogische Hochschule Heidelberg (PHHD) 2012, zur Verfügung gestellt von der Technischen Informationsbibliothek (TIB), doi:10.5446/19898.