Meine Merkliste

Home
Lexikon
Fibonacci-Folge

Fibonacci-Folge

Die Fibonacci-Folge ist eine mathematische Folge nichtnegativer ganzer Zahlen, den Fibonacci-Zahlen.

Weiteres empfehlenswertes Fachwissen

Empfindlichkeitsprüfung von Laborwaagen

Leitfaden für die Waagenreinigung: 8 einfache Schritte

Was ist der richtige Weg, um die Wiederholbarkeit bei Waagen zu überprüfen?

Inhaltsverzeichnis

1 Definition der Fibonacci-Folge
2 Eigenschaften
3 Berechnung
4 Geschichte
- 4.1 Modell einer Kaninchenpopulation
5 Trivia
6 Literatur
7 Einzelnachweise

Definition der Fibonacci-Folge

Die Fibonacci-Folge $(f_0, f_1,\ldots)$ ist durch das rekursive Bildungsgesetz

$f_n = f_{n-1} + f_{n-2}\$ für $n\geq 2$

mit den Anfangswerten

$f_0=0\$ und $f_1=1\$

definiert. Das bedeutet in Worten:

Für die beiden ersten Zahlen werden die Werte null und eins vorgegeben.
Jede weitere Zahl ist die Summe ihrer beiden Vorgänger.

Daraus ergibt sich die Folge zu

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1.597, 2.584, 4.181, 6.765, 10.946, 17.711, 28.657, 46.368, 75.025, 121.393, 196.418, 317.811, 514.229, 832.040, 1.346.269, 2.178.309, ...

(Folge A000045 in OEIS)

Oft wird auch $f 0 = 0$ ausgelassen und die Fibonacci-Folge mit $f 1 = 1$ und $f 2 = 1$ beginnend definiert, insbesondere bei der Anwendung auf Situationen, in denen ein Anfangswert Null keinen Sinn hat.

Eigenschaften

Beziehungen zwischen den Folgegliedern

$f_{m+n} = f_{n+1} \; f_m + f_n \; f_{m-1}$
$f_{m+n} = f_n\; L_m + (-1)^{m+1} \; f_{n-m}$ mit der Lucas-Folge $L_m=f_{m+1}+\;f_{m-1}=\Phi^m+\Psi^m$ , insbesondere:
$f_{2n} = f_n\; L_n = f_n\; (f_{n+1}+f_{n-1})$
$\operatorname{ggT}(f_m,f_n)=f_{\operatorname{ggT}(m,n)}$
$m\mid n\implies f_m\mid f_n$ ; falls $m > 2$ ist, gilt auch die Umkehrung. Insbesondere kann $f n$ für $n > 4$ nur dann eine Primzahl sein, wenn $n$ eine Primzahl ist.

Identität von Catalan:

$f_{n}^2 - f_{n+k} \; f_{n-k}=(-1)^{n-k} f_{k}^2$

Identität von Cassini, Spezialfall der Catalan-Identität:

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

Identität von d'Ocagne:

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

Es gibt noch zahlreiche weitere derartige Formeln.

Verwandtschaft mit dem Goldenen Schnitt

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

$\frac {f_{n+1}}{f_n} \approx {\Phi^{n+1}\over\Phi^n} = \Phi \approx 1{,}618{...}$

Diese Quotienten zweier aufeinander folgender Fibonacci-Zahlen haben eine bemerkenswerte Kettenbruchdarstellung

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

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

$\Phi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+. ..}}}}$

darstellen.

Φ ist eine irrationale Zahl. Es zeigt sich, dass sie in einem bestimmten Sinne die irrationalste aller Zahlen ist. Das bedeutet, dass sie sich nur schlecht durch ein Verhältnis zweier ganzer Zahlen annähern lässt, ein Umstand, der wesentlich zu ihrer Bedeutung in Kunst und Natur beiträgt. Am besten lässt sich Φ durch Quotienten zweier aufeinander folgender Fibonacci-Zahlen darstellen.

Zeckendorf-Theorem

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

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

Die entstehende Folge $(c)$ von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Aus der Definition der Fibonacci-Zahlen folgt, dass keine zwei Einsen in einer Zeckendorf-Sequenz hintereinander stehen können.

Fibonacci-Folgen in der Natur

Viele Pflanzen weisen in ihrem Bauplan Spiralen auf, deren Anzahl durch Fibonacci-Zahlen gegeben sind, wie beispielsweise bei den Samen in Blütenständen. Das ist dann der Fall, wenn der Winkel zwischen architektonisch benachbarten Blättern oder Samen bezüglich der Pflanzenachse der Goldene Winkel ist. Hintergrund ist der Umstand, dass die rationalen Zahlen, die den zugrunde liegenden Goldenen Schnitt am besten approximieren, Brüche von aufeinanderfolgenden Fibonacci-Zahlen sind. Die Spiralen werden daher von Pflanzenelementen gebildet, deren Platznummern sich durch die Fibonacci-Zahl im Nenner unterscheiden und damit fast in die gleiche Richtung weisen.

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

Ein weiterer interessanter Aspekt ist, dass die Fibonacci-Folge die Ahnenmenge einer weiblichen Honigbiene (Apis mellifera) beschreibt. Das erklärt sich dadurch, dass Bienendrohnen sich aus unbefruchteten Eiern entwickeln, die in ihrem Genom dem Erbgut der Mutter entsprechen.

Berechnung

Formel von Binet

Die Fibonacci-Zahlen lassen sich auch direkt über eine Formel berechnen:

${f_n=\frac{\Phi^n - \Psi^n}{\Phi \;\; - \Psi \;\; };} \qquad {n \in \mathbb{Z};} \qquad {\Phi = \frac{1+\sqrt{5}}{2};} \qquad {\Psi =\frac{1-\sqrt{5}}{2}.}$

Mit dem Goldenen Schnitt $Φ$ und seinem algebraisch konjugiertem $Ψ$ eingesetzt, ergibt dies die ursprünglich vom französischen Mathematiker Jacques Philippe Marie Binet anno 1843 veröffentlichte geschlossene Formel:

$f_n=\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 ${Φ,Ψ}$ , welches zu einem ganzzahligen Ergebnis führt. Diese Formel lässt sich mit dem Ansatz $f (n) = a n$ herleiten. Aus der Rekursionsformel folgt: $a 2 = a + 1$ . Die Lösung dieser quadratischen Gleichung ergibt ${Φ,Ψ}$ und führt später zur obigen Formel.

Herleitung der Formel von Binet

Die Formel von Binet kann mit Matrizenrechnung und dem Eigenwertproblem in der Linearen Algebra hergeleitet werden, folgender Ansatz: $\left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right]^{n}\left[ \begin{array}{c} F_{0} \\ F_{1} \end{array} \right]=\left[ \begin{array}{c} F_{n} \\ F_{n+1} \end{array} \right]\; ,\; F_{0}=0\; und\; F_{1}=1\; mit\; n\geq 0$

Um das Problem zu lösen, transformiert man die Matrix $A=\left[ \begin{array}{cc} 0 & 1 \\ 1 & 1 \end{array} \right]$ in eine Diagonalmatrix D und dies geht nur über das Eigenwertproblem.

$A=TDT^{-1}\;$ wobei T die Matrix der Eigenvektoren und D die Diagonalmatrix mit den Eigenwerten ist. Das Problem kann nun wie folgt geschrieben werden und führt zur Lösung:

$\left( TDT^{-1} \right)^{n}\left[ \begin{array}{c} 0 \\ 1 \end{array} \right]=TD^{n}T^{-1}\left[ \begin{array}{c} 0 \\ 1 \end{array} \right]=\left[ \begin{array}{c} F_{n} \\ F_{n+1} \end{array} \right]=\left[ \begin{array}{c} -\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} \\ -\frac{1}{\sqrt{5}}\left( \frac{1-\sqrt{5}}{2} \right)^{n}+\frac{1}{\sqrt{5}}\left( \frac{1+\sqrt{5}}{2} \right)^{n} \end{array} \right]\;$

Eine zweite Herleitung

Eine andere Möglichkeit erhält man durch folgenden Ansatz:

Für die Potenzfunktion $p (n) = x n$ gilt für alle $n\in \mathbb{N}$ $p(n+2) - p(n+1) - p(n) = (x^2 - x -1) \cdot p(n)$ durch Herausheben.

Wenn also x so gewählt wird, dass $x 2 - x - 1 = 0$ ist, wird $p (n + 2) = p (n + 1) + p (n)$ , also die Rekursion der Fibonaccifolge. Das tritt ein, wenn x das reziproke Teilverhältnis $Φ$ des goldenen Schnitts oder sein algebraisch Konjugiertes $Ψ$ ist. Die Fibonaccische Rekursionsformel wird also auch erfüllt durch $g (n) = a Φ n + b Ψ n$ .

Nun bestimme man die Koeffizienten a und b so, dass wie bei der Fibonaccifolge $g (0) = 0$ und $g (1) = 1$ wird. Dazu sind zwei einfache lineare Gleichungen zu lösen. Dann kommt die Binet-Formel heraus.

Erzeugende Funktion

Die erzeugende Funktion der Fibonacci-Zahlen ist

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

Die auf der linken Seite stehende Potenzreihe konvergiert für $| z | < 1 / Φ$ .

Schreibt man die obige erzeugenden Funktion als Verknüpfung zweier Potenzreihen im Sinne der formalen Potenzreihen so erhält man $(1-z)^{-1} \circ (z+z^2)$ . Als Potenzreihe geschrieben ergibt das $\sum_{l\geq 0} (z+z^2)^l= \sum_{l\geq 0} z^l \sum_{k=0}^{l} \tbinom l k z^k$ nach Herausheben sowie Umschreiben der Summe als Binomialreihe. Die letzte Summe kann mittels Umbenennung der Summationsindizes vereinfacht werden zu $\sum_{0 \leq k \leq l} \tbinom l k z^{l+k} = \sum_{n \geq 0} z^n \sum_{k=0}^{n} \tbinom {n-k} {k}$ .

Koeffizientenvergleich liefert für $f_{n} = \sum_{k=0}^{n} \tbinom {n-k} {k}$ .

Darstellung mit Matrizen

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

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

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

Näherungsformel für große Zahlen

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

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

Im Unterschied beispielsweise zur Stirling-Formel wird diese Formel für wachsende $n$ immer genauer; bei der Stirling-Formel geht lediglich der relative Fehler gegen 0.

Der Absolutbetrag des Quotienten $\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$ .

Geschichte

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.)^[1]. 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 es zuerst der italienische Mathematiker Leonardo da Pisa, genannt Fibonacci („figlio di Bonacci“, Sohn des Bonacci), 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^[2]:

Modell einer Kaninchenpopulation

Fibonacci illustrierte diese Folge durch die einfache mathematischen Modellierung des Wachstums einer Kaninchenpopulation nach folgender Vorschrift:

Zu Beginn gibt es ein Paar geschlechtsreifer Kaninchen.
Jedes neugeborene Paar wird im zweiten Lebensmonat geschlechtsreif.
Jedes geschlechtsreife Paar wirft pro Monat ein weiteres Paar.
Die Tiere befinden sich in einem abgeschlossenen Raum („in quodam loco, qui erat undique pariete circundatus“), so dass kein Tier die Population verlassen und keines von außen hinzukommen kann.

Das erste Paar erzeugt seinen Nachwuchs bereits im ersten Monat. Jeden Folgemonat kommt dann zu der Anzahl der Paare, die im letzten Monat gelebt haben, eine Anzahl von neugeborenen Paaren hinzu, die gleich der Anzahl der Paare ist, die bereits im vorletzten Monat gelebt haben, da genau diese geschlechtsreif sind und sich nun vermehren. Fibonacci führte den Sachverhalt für die zwölf Monate eines Jahres vor (1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377) und weist auf die Bildung der Reihe durch Addition mit dem jeweils vorhergehenden Reihenglied hin (1+2=3, 2+3=5, 3+5=8, etc.). Er merkte außerdem an, dass die Folge sich − unter der Annahme unsterblicher Kaninchen − unendlich fortsetzen lässt: „et sic posses facere per ordinem de infinitis numeris mensibus.“ Weitere Beachtung hatte er dem Prinzip in seinen erhaltenen Werken nicht geschenkt.

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

Trivia

Das Systemgedicht "alfabet" (1981) der dänischen Schriftstellerin Inger Christensen basiert auf der Fibonacci-Folge.
Die Rock-Band Tool bedient sich in ihrem Song „Lateralus“ (vom gleichnamigen Album von 2001) der Fibonacci-Folge und lässt die Silben der Strophentexte im entsprechenden Rhythmus erklingen. Ebenso wurde ein Lied über die Fibonacci-Sequenz von Dr. Steel geschrieben.
Die Fibonacci-Folge findet Erwähnung in Dan Browns Roman „Sakrileg“ und im Roman "Der Kern des Bösen" von Tiberius Maczek (2007).
Des Weiteren ist diese Folge im Film Pi relevant.

Literatur

Hans Magnus Enzensberger, Der Zahlenteufel, ISBN 3-446-18900-9
John H. Conway und Richard K. Guy, The Book of Numbers, ISBN 0-387-97993-X
Paolo Ribenboim, The New Book of Prime Number Records, ISBN 0-387-94457-5

Einzelnachweise

↑ Parmanand Singh: Acharya Hemachandra and the (so called) Fibonacci Numbers. In: Mathematics Education 20,1 (Siwan, 1986), S. 28-30, ISSN 0047-6269]
↑ 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“)
↑ 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

Kategorie: Theoretische Biologie

Dieser Artikel basiert auf dem Artikel Fibonacci-Folge aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar.