Fibonacci-Folge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Kachelmuster aus Quadraten, deren Kantenlängen der Fibonacci-Folge entsprechen

Die Fibonacci-Folge ist die unendliche Folge von natürlichen 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:

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

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 der Pflanzen 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.
  • Die Fibonacci-Folge steht in einem unmittelbaren Zusammenhang zum Goldenen Schnitt. Je größer die Zahl der Reihe wird, desto mehr nähert sie sich dem Goldenen Schnitt (1,618033...) als Ergebnis der Division mit der vorhergehenden Zahl (beispielsweise 13:8=1,6250; 21:13=1,6154; 34:21=1,6190; 55:34=1,6176; etc).
  • Die Annäherung ist dabei auch noch symmetrisch, d.h. je eine Division nähert sich dem Goldenen Schnitt abwechselnd von oben (ist größer als der Goldene Schnitt) und die darauf folgende Division von unten (ist kleiner als der Goldene Schnitt). Das ist bemerkenswert, da die Natur ebenfalls dem Prinzip der Symmetrie zu folgen scheint.[3]

Definition der Fibonacci-Folge[Bearbeiten]

Die Fibonacci-Folge f_1,\,f_2,\,f_3,\ldots ist durch das rekursive Bildungsgesetz

f_n = f_{n-1} + f_{n-2}   für n > 2

mit den Anfangswerten

f_1 = f_2 = 1

definiert. Das bedeutet in Worten:

  • Für die beiden ersten Zahlen wird der Wert eins 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

f_n = f_{n-1} + f_{n-2}

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

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

Die so erweiterte Fibonacci-Folge lautet dann

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

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

Eigenschaften[Bearbeiten]

Beziehungen zwischen den Folgegliedern[Bearbeiten]

Identitäten:

Teilbarkeit:

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

Reihen:

  • \sum_{i=0}^{n} f_i = f_{n+2}-1
  • \sum_{i=1}^{2n} (-1)^{i-1} \; f_i = -f_{2n-1}+1
  • \sum_{i=1}^{2n+1} (-1)^{i-1} \; f_i = f_{2n}+1
  • \sum_{i=1}^{n} f_i^2 = f_n \; f_{n+1}
  • \sum_{i=1}^{n} f_{2i-1} = f_{2n}
  • \sum_{i=1}^{n} f_{2i} = f_{2n+1}-1

Es gibt noch zahlreiche weitere derartige Formeln.

Verwandtschaft mit dem Goldenen Schnitt[Bearbeiten]

Wie von Johannes Kepler festgestellt wurde, nähert sich der Quotient zweier aufeinander folgender Fibonacci-Zahlen dem Goldenen Schnitt Φ an. Dies folgt unmittelbar aus der Näherungsformel für große n:

\lim_{n \to \infty}\frac {f_{n+1}}{f_n} = \lim_{n \to \infty}{\Phi^{n+1}\over\Phi^n} = \Phi \approx 1{,}618\ldots

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

\frac{1}{1} = 1 \qquad \frac{2}{1} = 1+\frac{1}{1} \qquad \frac{3}{2} = 1+\frac{1}{1+ \frac{1}{1}} \qquad \frac{5}{3} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1}}} \qquad \frac{8}{5} = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1}}}}

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

\Phi = 1+\cfrac{1}{1+ \cfrac{1}{1+ \cfrac{1}{1+ \cfrac{1}{1+\dotsb}}}}

darstellen.

Die Zahl Φ ist irrational. Das bedeutet, dass sie sich nicht durch ein Verhältnis zweier ganzer Zahlen darstellen lässt. Am besten lässt sich Φ durch Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen approximieren. Dies gilt auch für verallgemeinerte Fibonaccifolgen, bei denen f_0 und f_1 beliebige natürliche Zahlen annehmen.

Zeckendorf-Theorem[Bearbeiten]

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

n = \sum_{i=2}^{k} c_i f_i \quad\ c_i\in \{0, 1\}; \forall i: c_ic_{i+1}=0.

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

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

z = \sum_{i=1}^{k} c_i f_{-i} \quad\ c_i\in \{0, 1\}; \forall i: c_ic_{i+1}=0

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

Fibonacci-Folgen in der Natur[Bearbeiten]

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

Viele Pflanzen weisen in der Anordnung ihrer Blätter und anderer Teile Spiralen auf, deren Anzahlen durch Fibonacci-Zahlen gegeben sind, wie beispielsweise bei den Früchten in Fruchtständen. Das ist dann der Fall, wenn der Winkel zwischen architektonisch benachbarten Blättern oder Früchten bezüglich der Pflanzenachse der Goldene Winkel ist. Hintergrund ist der Umstand, dass die rationalen Zahlen, die den zugrunde liegenden Goldenen Schnitt am besten approximieren, Brüche von aufeinanderfolgenden Fibonacci-Zahlen sind. Die Spiralen werden daher von Pflanzenelementen gebildet, deren Platznummern sich durch die Fibonacci-Zahl im Nenner unterscheiden und damit fast in die gleiche Richtung weisen. Durch diese spiralförmige Anordnung der Blätter um die Sprossachse erzielt die Pflanze die beste Lichtausbeute. Der Versatz der Blätter um das irrationale Verhältnis des Goldenen Winkels sorgt dafür, dass nie Perioden auftauchen, wie es z. B. bei 1/4 der Fall wäre (0° 90° 180° 270° | 0° 90° …). Dadurch wird der denkbar ungünstigste Fall vermieden, dass ein Blatt genau senkrecht über dem anderen steht und sich so die jeweils übereinanderstehenden Blätter maximalen Schatten machen oder maximale ‚Lichtlücken‘ entstehen.

Beispielsweise tragen die Kö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.[7] 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.[8]

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

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

Berechnung[Bearbeiten]

Formel von Moivre/Binet[Bearbeiten]

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

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

Die Fibonacci-Zahlen lassen sich direkt mittels

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

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

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

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

f_n = \frac{\varphi^n-\psi^n}{\sqrt5}
           = \frac1{\sqrt 5} \left[\Phi^n- \left(-\frac1{\Phi}\right)^n\right]
           = \frac1{\sqrt 5} \left[ \left(\frac{1+\sqrt 5}2\right)^n - \left(\frac{1-\sqrt 5}2\right)^n \right]

Bemerkenswert ist das Zusammenspiel zweier irrationaler Zahlen φ und ψ, das zu einem ganzzahligen Ergebnis führt. Die Abbildung zeigt die beiden Teilfolgen mit φ und ψ sowie deren Differenz. Der Einfluss von ψn geht rasch gegen Null. Das kann man verwenden, um die Berechnung zu beschleunigen, indem man den Term ignoriert und das Ergebnis zur nächstgelegenen natürlichen Zahl rundet.

Induktiver Beweis[Bearbeiten]

Einer der einfachsten Beweise gelingt induktiv. Wegen \tfrac{\varphi^0-\psi^0}{\sqrt5} = 0 = f_0 und \tfrac{\varphi^1-\psi^1}{\sqrt5} = 1 = f_1 ist der Induktionsanfang erfüllt. Angenommen die Formel gelte für alle Werte bis n. Wir zeigen nun, dass sie dann notwendigerweise auch für n+1 gelten muss:

f_{n-1}+f_n = \frac{\varphi^{n-1}-\psi^{n-1}+\varphi^n-\psi^n}{\sqrt5}
                   = \frac{\varphi^n(1+\frac1{\varphi})-\psi^n(1+\frac1{\psi})}{\sqrt5}
                   = \frac{\varphi^{n+1}-\psi^{n+1}}{\sqrt5}
                   = f_{n+1}

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

Nach dem Prinzip der vollständigen Induktion muss nun die Formel für alle n gelten.

Herleitung der Formel von Moivre-Binet[Bearbeiten]

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

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

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

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


\begin{align}
\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^nT^{-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{align}

Herleitung mittels Differenzengleichung[Bearbeiten]

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

Sei C_n = x^n, n\in\N_0 eine geometrische Folge, so ergibt sich:

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

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

Die rekursive Folge A_0=1, A_1=\varphi, A_{n+1} = A_n + A_{n-1} hat die explizite Darstellung A_n=\varphi^n. Ebenso B_0=1, B_1=\psi, B_n=\psi^n.

Mit A_n und B_n genügt wegen der Superpositionseigenschaft auch jede Linearkombination L_n=\alpha A_n + \beta B_n der Fibonacci-Rekursion L_{n+1} = L_n + L_{n-1}. Mit Hilfe eines linearen Gleichungssystems ergibt sich \alpha=\tfrac{1}{\sqrt5} und \beta=-\tfrac{1}{\sqrt5}, damit L_0=\tfrac{\varphi^0-\psi^0}{\sqrt5} = 0 = f_0 und L_1=\tfrac{\varphi^1-\psi^1}{\sqrt5} = 1 = f_1. Folglich ergibt sich explizit F_n = \tfrac{A_n-B_n}{\sqrt5} = \tfrac{\varphi^n-\psi^n}{\sqrt5}.

Für \alpha=\beta=1 ergibt sich L_0=2 und L_1=1, d. h. die klassische Lucas-Folge mit explizit L_n = A_n+B_n = \varphi^n+\psi^n.

Erzeugende Funktion[Bearbeiten]

Die erzeugende Funktion der Fibonacci-Zahlen ist

\sum_{n=0}^\infty f_n z^n = \frac{z}{1-z-z^2}.

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

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

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

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

Koeffizientenvergleich liefert schließlich \textstyle f_n = \sum_{k=0}^n \tbinom {n-k-1} {k}.

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

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

Darstellung mit Matrizen[Bearbeiten]

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

\begin{pmatrix}1&1\\1&0\end{pmatrix}^n=\begin{pmatrix}f_{n+1}&f_n\\f_n&f_{n-1}\end{pmatrix}

Aus der Relation A^{m+n}=A^mA^n ergibt sich beispielsweise die erste oben angegebene Formel für f_{m+n}. A beschreibt zugleich die Summationsvorschrift der Fibonacci-Folge, denn ihr Produkt mit einem Paar aufeinanderfolgender Fibonacci-Zahlen (als Spaltenmatrix geschrieben) ergibt das nächste Paar; entsprechend erzeugt A^n das n-te Paar aus dem Startpaar (0,1). Dies und die Tatsache, dass die Eigenwerte von A gerade der Goldene Schnitt und dessen Kehrwert (letzterer mit negativem Vorzeichen) sind, führen wieder auf die oben genannte Formel von Binet.

Näherungsformel für große Zahlen[Bearbeiten]

Für große Werte von n wird \psi^n = \left(\tfrac{1-\sqrt{5}}{2} \right)^n in der Formel von Binet immer kleiner, da der Ausdruck in der Klammer vom Betrag kleiner als 1 ist. Deshalb erhält man die Näherungsformel

f_n \approx \frac{1}{\sqrt{5}} {\phi}^n = \frac{1}{\sqrt{5}} \cdot \left(\frac{1+\sqrt{5}}{2} \right)^n.

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

f_n = \left\lfloor\frac{1}{\sqrt{5}} {\phi}^n + \frac{1}{2}\right\rfloor = \left\lfloor\frac{1}{\sqrt{5}} \cdot \left(\frac{1+\sqrt{5}}{2} \right)^n + \frac{1}{2}\right\rfloor

mit der Gaußklammer \lfloor{\cdot}\rfloor.

Verallgemeinerungen[Bearbeiten]

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

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

Jedes dieser Kriterien erlaubt eine Verallgemeinerung:

  • Die Wahl anderer Startglieder u und v liefert eine Folge (a_n), die mit der kanonischen Folge nach der Beziehung a_n=u\cdot f_{n-2}+v\cdot f_{n-1} zusammenhängt. Ein Beispiel hierfür ist die Lucas-Folge (L_n).
Für die Glieder einer solchen Folge gilt ein gegenüber der Formel von Moivre-Binet verallgemeinertes explizites Bildungsgesetz:
a_n\!\,= \frac{k\cdot \varphi^n-l\cdot \psi^n}{\sqrt5} mit k=u\cdot \psi^2-v\cdot \psi und l=u\cdot \varphi^2-v\cdot \varphi.
Die kanonische Folge stellt sich hier als Spezialfall mit u=v=1 dar, was wegen der charakteristischen Gleichung sofort k=1 und l=1 liefert.
  • Die Wahl anderer Koeffizienten für die Linearkombination liefert eine Folge, für die eine andere charakteristische Gleichung gilt. Eine Folge mit der Iterationsvorschrift
a_n=q\cdot a_{n-2}+p\cdot a_{n-1}
besitzt die charakteristische Gleichung x^2-px-q=0. Die Wurzeln dieser Gleichung bestimmen das explizite Bildungsgesetz. Wenn die charakteristische Gleichung die Wurzeln \alpha und \beta hat, dann lautet das Bildungsgesetz
a_n=\frac{k\cdot \alpha^n-l\cdot \beta^n}{\alpha-\beta},
wobei k und l wieder durch die Startglieder bestimmt sind.
  • Eine Iteration, die mehr als zwei vorangehende Folgenglieder einbezieht, besitzt dementsprechend ein Polynom höheren Grades als charakteristische Gleichung, wobei die Wurzeln x_i dieser Gleichung wieder im Bildungsgesetz auftauchen und die Koeffizienten k_i durch die Anfangswerte bestimmt sind. Es gilt dann
a_n=\sum_{i=1}^n {k_ix_i^n}.
Eine Iteration, die nur das unmittelbar vorhergehende Glied verwendet, liefert in diesem Zusammenhang als entartete Fibonacci-Folge eine reine Potenzfolge.

Geschichte[Bearbeiten]

Berechnung der Kaninchenaufgabe im Liber abbaci

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

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

Modell einer Kaninchenpopulation[Bearbeiten]

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

  1. Jedes Paar Kaninchen wirft pro Monat ein weiteres Paar Kaninchen.
  2. Ein neugeborenes Paar bekommt erst im zweiten Lebensmonat Nachwuchs (die Austragungszeit reicht von einem Monat in den nächsten).
  3. Die Tiere befinden sich in einem abgeschlossenen Raum („in quodam loco, qui erat undique pariete circundatus“), sodass kein Tier die Population verlassen und keines von außen hinzukommen kann.

Fibonacci begann die Reihe, nicht ganz konsequent, nicht mit einem neugeborenen, sondern mit einem trächtigen Paar, das seinen Nachwuchs bereits im ersten Monat wirft, 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 Reihe durch Summierung jeweils zweier aufeinanderfolgender Reihenglieder (2+3=5, 3+5=8, 5+8=13 usw.) hin. Er merkte außerdem an, dass die Reihe sich nach diesem Prinzip für eine unendliche Zahl von Monaten fortsetzen lässt, was dann allerdings unsterbliche Kaninchen voraussetzt: „et sic posses facere per ordinem de infinitis numeris mensibus.“ Weitere Beachtung hatte er dem Prinzip in seinen erhaltenen Werken nicht geschenkt.

Eine gerade 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.[13]

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

Martina Schettina: Fibonaccis Traum, 2008, 40×40 cm
Petra Paffenholz: Fibonacci Cubes (Teil des Skulpturenpfades „Diepholz | Dümmer“), 2014, 10 cm bis 5,50 m

Rezeptionen in Kunst und Unterhaltung[Bearbeiten]

  • 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.[15]
  • Die Künstler Mario Merz und Petra Paffenholz setzten sich in ihren Installationen mit der Fibonacci-Folge auseinander.
  • Der Gesang im Lied Lateralus der Progressive-Metal-Band Tool basiert auf Fibonacci-Zahlen.[16]
  • Die Künstlerin Martina Schettina beschäftigt sich in ihren mathematischen Bildern ebenfalls mit den Fibonacci-Zahlen.[17][18]
  • 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.[19]
  • In dem Song What´s Goes von Die Orsons rappt KAAS die Fibonacci-Folge bis zur Zahl 144. [20]

Fibonacci-Datenstrukturen[Bearbeiten]

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

Literatur[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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 Der goldene Schnitt, golden-section.eu, Dr. Dr. Ruben Stelzner in Zusammenarbeit mit Prof. Dr. Wolfgang Schad, abgerufen am 26. Oktober 2015
  4. Nicolai N. Vorobiev: Fibonacci Numbers. Birkhäuser, Basel 2002. ISBN 3-7643-6135-2. S. 59, Online-Version.
  5. PDF. Bei: sternenreise.com.
  6.  Donald E. Knuth: The Art Of Computer Programming Vol. IV.
  7. G. Hegi: Illustrierte Flora von Mitteleuropa. Band VI/4. 2. Auflage 1987. Weissdorn Verlag, Jena. ISBN 3-936055-23-8.
  8. Richard A. Dunlap: The Golden Ratio and Fibonacci Numbers. World Scientific, Singapur, 1999, ISBN 981-02-3264-0, S. 130–134.
  9. 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 3540420320, 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 9783827423498, S. 46 (Auszug (Google))) oder Ben-Menahem (Ari Ben-Menahem: Historical Encyclopedia of Natural and Mathematical Sciences. Band 1. Springer 2009, ISBN 9783540688310, S. (Auszug (Google)))
  10. Parmanand Singh: Acharya Hemachandra and the (so called) Fibonacci Numbers. In: Mathematics Education. 20,1 (Siwan, 1986), S. 28–30, ISSN 0047-6269.
  11. 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.
  12. 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“).
  13. T.C. Scott, P. Marketos: On the Origin of the Fibonacci Sequence (Englisch, PDF) MacTutor History of Mathematics archive, University of St Andrews. March, 2014.
  14. 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.
  15. Grab That Gun. Auf: en.wikipedia.
  16. Graham Hartmann: „No. 1: Tool, ‘Lateralus’ – Top 21st Century Metal Songs.“ Bei: loudwire.com. Aufgerufen am 22. Februar 2014.
  17. Beitrag in MU – Der Mathematikunterricht „Mathematik und Kunst“ Jg 55 – Heft 2 – April 2009 – Friedrich Verlag, Herausgeber Stefan Deschauer TU Dresden ISSN-Nr. 0025-5807
  18. Ingmar Lehmann: Fibonacci-Zahlen in Bildender Kunst und Literatur. Abgerufen am 7. November 2009 (PDF; 131 kB).
  19. Missing Persons. Bei: watchdogs.wikia.com.
  20. [1]