Fibonacci-Folge

Die Fibonacci-Folge ist die unendliche Folge natürlicher Zahlen, die mit zweimal der Zahl 1 beginnt, und bei der jede Zahl die Summe der beiden ihr vorangehenden Zahlen ist. In moderner Schreibweise wird diese Folge zusätzlich mit einer führenden Zahl 0 versehen:^[1]

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:

• Aufgrund der Beziehung zur vorherigen und zur folgenden Zahl scheint Wachstum in der Natur einem Additionsgesetz zu folgen.
• Je weiter man in der Folge fortschreitet, desto mehr nähert sich der Quotient aufeinanderfolgender Fibonacci-Zahlen dem Teilungsverhältnis des Goldenen Schnittes ${\displaystyle \Phi =1{,}6180\ldots }$ (beispielsweise 13:8 = 1,6250; 21:13 ≈ 1,6154; 34:21 ≈ 1,6190; 55:34 ≈ 1,6176; etc.). Diese Näherung ist alternierend, d. h., die Quotienten sind abwechselnd kleiner und größer als ${\displaystyle \Phi }$.^[3]

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.^{[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 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.^[4]

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

Zu den zahlreichen bemerkenswerten Eigenschaften der Fibonacci-Zahlen gehört, dass sie dem Benfordschen Gesetz genügen.^[6]

Wie von Johannes Kepler festgestellt wurde, kommen die Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen dem Goldenen Schnitt

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

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 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 dem Artikel Kettenbruch.

Da diese Quotienten gegen den Goldenen Schnitt konvergieren, lässt sich dieser als der unendliche periodische Kettenbruch darstellen:

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

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.

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}$

Summenformeln:

• ${\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}$
• ${\displaystyle \sum _{i=0}^{n}{\binom {n}{i}}f_{i}=f_{2n}}$
• ${\displaystyle \sum _{i=0}^{n}{\binom {n-i}{i}}=f_{n+1}}$

Es gibt 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]

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.

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 es aber auch den Mathematikern Leonhard Euler und Daniel Bernoulli bekannt, Letzterer lieferte 1728 auch den vermutlich ersten Beweis.^[11]

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}}$

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.

Der Einfluss von ${\displaystyle \Psi }$ geht rasch gegen Null, bspw. ist ${\displaystyle -\Psi /{\sqrt {5}}\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} }$.

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.

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}}}$

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 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}}$.

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.

Die Quotienten aufeinanderfolgender Glieder der Fibonacci-Folge sind abwechselnd kleiner und größer als der Goldene Schnitt:^[12]

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

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.

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

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

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

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}=\sum _{k=0}^{n-1}{\tbinom {n-k-1}{k}}=\sum _{k=1}^{n}{\tbinom {n-k}{k-1}}\quad (n\geq 1)}$

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).}$

Wertet man die erzeugende Funktion an der Stelle ${\displaystyle x=1/10}$ aus, so erhält man ${\displaystyle 10/89}$, folglich lässt sich ${\displaystyle 89^{-1}}$ in eine unendliche Summe von Fibonacci-Zahlen zur Basis ${\displaystyle 10^{-n-1}}$ zerlegen.

${\displaystyle {\begin{aligned}1/89&=0.0112359550\dots \\&=0+1\cdot 10^{-2}+1\cdot 10^{-3}+2\cdot 10^{-4}+3\cdot 10^{-5}+5\cdot 10^{-6}+8\cdot 10^{-7}+13\cdot 10^{-8}+21\cdot 10^{-9}+\dots \end{aligned}}}$

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.

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.

Da die Fibonacci-Zahlen exponentiell mit dem Index wachsen, konvergieren die 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