Fibonacci-Folge

Grundidee und Definition

Die Fibonacci-Folge ist eine unendliche Folge natürlicher Zahlen. Sie beginnt klassisch mit zweimal der Zahl 1; in moderner Schreibweise wird oft noch eine führende 0 ergänzt: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 … Die Zahlen der Folge heißen Fibonacci-Zahlen.

Formal ist die Folge durch die Rekursion f_n = f_{n-1} + f_{n-2} für n ≥ 3 mit den Anfangswerten f_1 = f_2 = 1 definiert. Rekursion bedeutet: Ein neues Folgenglied wird aus vorherigen Folgengliedern berechnet. In Worten: Die ersten beiden Zahlen sind 1, jede weitere Zahl ist die Summe ihrer beiden Vorgänger.

Aus der Definition folgen zum Beispiel f_3 = 2, f_4 = 3, f_5 = 5, f_10 = 55, f_20 = 6765 und f_50 = 12 586 269 025. Durch Umstellen der Rekursion kann man die Folge auch rückwärts fortsetzen. Dann gilt f_0 = 0 und allgemein f_{-n} = (-1)^{n+1} f_{+n}. Dadurch entsteht die Folge der negaFibonacci-Zahlen, etwa …, +34, −21, +13, −8, +5, −3, +2, −1, +1, 0, 1, 1, 2, 3, 5 …

Goldener Schnitt und wichtige Eigenschaften

Eine zentrale Eigenschaft ist die Beziehung zum Goldenen Schnitt. Der Goldene Schnitt ist die Zahl Φ := (1 + √5) / 2 ≈ 1,6180. Wie Johannes Kepler feststellte, nähern sich die Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen dieser Zahl beliebig genau an: lim_{n→∞} f_{n+1} / f_n = Φ. Beispiele sind 13 : 8 = 1,6250, 21 : 13 ≈ 1,6154, 34 : 21 ≈ 1,6190 und 55 : 34 ≈ 1,6176.

Diese Annäherung ist alternierend: Die Quotienten liegen abwechselnd unter und über Φ. Genauer gilt für natürliche n > 0: f_{2n} / f_{2n-1} < Φ < f_{2n+1} / f_{2n}. Die Differenz zwischen oberer und unterer Schranke wird schnell klein, weil sie gleich 1 / (f_{2n} f_{2n-1}) ist.

Die Fibonacci-Zahlen besitzen viele Identitäten. Beispiele sind f_{2n} = f_n (f_{n+1} + f_{n-1}), f_{2n+1} = f_n^2 + f_{n+1}^2 sowie die Identität von Cassini: f_{n+1} f_{n-1} − f_n^2 = (−1)^n. Bei der Teilbarkeit gilt unter anderem ggT(f_m, f_n) = f_{ggT(m,n)}; benachbarte Fibonacci-Zahlen sind teilerfremd, also ggT(f_n, f_{n+1}) = 1. Außerdem ist genau jede dritte Fibonacci-Zahl durch 2, jede vierte durch 3 und jede fünfte durch 5 teilbar.

Das Zeckendorf-Theorem besagt: Jede natürliche Zahl n > 0 lässt sich eindeutig als Summe verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen schreiben. Formal gibt es eine eindeutige Darstellung n = Σ_{i=2}^{k} c_i f_i mit c_i ∈ {0,1} und c_i c_{i+1} = 0 für alle i. Die Folge der Nullen und Einsen heißt Zeckendorf-Sequenz.

Berechnungsmethoden

Neben der rekursiven Berechnung gibt es direkte Formeln. Die Formel von Moivre-Binet wurde unabhängig von Abraham de Moivre im Jahr 1718 und Jacques Philippe Marie Binet im Jahr 1843 entdeckt; sie war auch Leonhard Euler und Daniel Bernoulli bekannt. Sie lautet für n ∈ ℤ: f_n = (Φ^n − Ψ^n) / (Φ − Ψ), wobei Φ und Ψ die Lösungen der charakteristischen Gleichung x^2 − x − 1 = 0 sind. Dabei ist Φ = (1 + √5) / 2 und Ψ = 1 − Φ = (1 − √5) / 2 = −Φ^{-1}. Da Φ − Ψ = √5, gilt auch f_n = (Φ^n − Ψ^n) / √5.

Bemerkenswert ist, dass diese Formel mit irrationalen Zahlen arbeitet, aber ganze Fibonacci-Zahlen liefert. Für große n wird Ψ^n sehr klein. Deshalb kann man näherungsweise rechnen und anschließend auf die nächstgelegene ganze Zahl runden: f_n = ⌊ (1/√5) ((1 + √5)/2)^n + 1/2 ⌋ für alle n ≥ 0.

Die Formel kann auf mehreren Wegen hergeleitet werden: durch vollständige Induktion, über ein Eigenwertproblem mit Matrizen, über lineare Differenzengleichungen oder mit der z-Transformation. Eine Matrixdarstellung ist besonders kompakt: Für A = ((1,1),(1,0)) gilt A^n = ((f_{n+1}, f_n),(f_n, f_{n-1})). Daraus lassen sich weitere Formeln ableiten, weil A^{m+n} = A^m A^n gilt.

Auch erzeugende Funktionen beschreiben die Folge. Die erzeugende Funktion ist Σ_{n=0}^{∞} f_n z^n = z / (1 − z − z^2), sie konvergiert für |z| < 1/Φ = 0,618… Aus ihr folgt wieder die Formel von Moivre-Binet. Setzt man z = 1/10 ein, erhält man eine Verbindung zu 1/89: 1/89 = 0,01123595505617977528089887640449…; die Dezimalentwicklung beginnt also mit Fibonacci-Zahlen, wobei Überträge zu beachten sind.

Zusammenhänge mit anderen Folgen und Strukturen

Die Fibonacci-Zahlen hängen mit dem Pascalschen Dreieck zusammen. Eine Darstellung lautet für n ≥ 1: f_n = Σ_{k=0}^{⌊n/2⌋} binom(n-k-1, k). Anschaulich ergeben bestimmte flache Diagonalen im Pascalschen Dreieck Fibonacci-Zahlen; im Artikel werden als Beispiele Summen mit den Ergebnissen 13, 21 und 34 genannt. Eine weitere Formel nutzt jeden zweiten Koeffizienten der n-ten Zeile des Pascalschen Dreiecks, gewichtet mit Potenzen von 5, und teilt durch 2^{n-1}: f_n = (1 / 2^{n-1}) Σ_{j=0}^{⌊n/2⌋} P_{n,2j+1} 5^j.

Da die Fibonacci-Zahlen exponentiell wachsen, konvergieren Reihen aus ihren Kehrwerten. Zum Beispiel ist die Summe der Kehrwerte aller Fibonacci-Zahlen ungefähr 3,359885666243177553172011302918927 und nach André-Jeannin (1989) irrational. Für gerade und ungerade Indizes gibt der Artikel Darstellungen mit Lambert-Reihen beziehungsweise Jacobischen Thetafunktionen an.

Die klassische Fibonacci-Folge lässt sich verallgemeinern. Man kann andere Startwerte u und v wählen; dann hängt die entstehende Folge (a_n) mit der kanonischen Folge durch a_n = u f_{n-2} + v f_{n-1} zusammen. Ein Beispiel ist die Lucas-Folge. Man kann auch die Rekursion verändern, etwa a_n = q a_{n-2} + p a_{n-1}; dann bestimmt die charakteristische Gleichung x^2 − px − q = 0 die explizite Formel. Werden mehr als zwei Vorgänger einbezogen, entstehen Folgen wie die Tribonacci- und Tetranacci-Folge. Bei der Tribonacci-Folge gilt f_n = f_{n-1} + f_{n-2} + f_{n-3} für n ≥ 4; ihre ersten Glieder sind 0, 1, 1, 2, 4, 7 …

Naturbeispiele und Anwendungen

Die Fibonacci-Folge beschreibt in mehreren Beispielen Wachstum oder Anordnungen in der Natur. In der Phyllotaxis, also der Blatt- oder Fruchtstandsanordnung vieler Pflanzen, treten Spiralen auf, deren Anzahlen Fibonacci-Zahlen sind. Der Winkel zwischen benachbarten Blättern oder Früchten bezogen auf die Pflanzenachse ist dabei der Goldene Winkel. Weil Brüche aufeinanderfolgender Fibonacci-Zahlen den Goldenen Schnitt besonders gut approximieren, entstehen Spiralen, deren Platznummern sich um Fibonacci-Zahlen unterscheiden und fast in dieselbe Richtung zeigen.

Diese Anordnung verbessert die Lichtausbeute: Durch den irrationalen Goldenen Winkel entstehen keine einfachen Perioden wie bei 1/4 der Umdrehung, also 0°, 90°, 180°, 270° und wieder 0°. Dadurch steht nicht regelmäßig ein Blatt genau über einem anderen. Als Beispiele nennt der Artikel Sonnenblumen mit 34 und 55 Fibonacci-Spiralen, die Silberdistel Carlina acaulis mit 21-zu-55-, 34-zu-89- und 55-zu-144-Stellungen sowie Fichtenzapfen und Ananasfrüchte, deren Schuppen im und gegen den Uhrzeigersinn Spiralen mit aufeinanderfolgenden Fibonacci-Zahlen bilden.

Auch Stammbäume können zur Fibonacci-Folge führen. Bei Honigbienen entwickeln sich männliche Tiere, Drohnen, aus unbefruchteten Eiern und haben daher keinen Vater, aber eine Mutter. Eine Königin hat dagegen zwei Eltern. Die Anzahl der Ahnen einer Drohne in der n-ten Generation ist deshalb die n-te Fibonacci-Zahl f_n.

Ein weiteres Beispiel betrifft unverzweigte aliphatische Monocarbonsäuren, zu denen im Regelfall Fettsäuren gehören. Wenn Doppelbindungen nicht benachbart sind, folgt die Anzahl möglicher Verbindungen bei gegebener Kettenlänge der Fibonacci-Folge. Bei 18 C-Atomen ergeben sich 2.584 Varianten; Stearinsäure, Ölsäure, Linolsäure und Linolensäure sind vier Beispiele.

Geschichte und Rezeption

Die Folge ist nach Leonardo Fibonacci benannt, der sie 1202 in seinem Liber abbaci anhand einer Kaninchenpopulation beschrieb. Sie war jedoch schon vorher bekannt. In Indien findet sich eine frühe Erwähnung unter dem Namen mātrāmeru in der Chhandah-shāstra des Sanskrit-Grammatikers Pingala, datiert auf um 450 v. Chr. oder nach anderer Datierung um 200 v. Chr. Später behandelten Virahanka im 6. Jahrhundert und Acharya Hemachandra (1089–1172) die Folge bei der Beschreibung von Metren aus kurzen und langen Silben. In der westlichen Antike kannte Nikomachos von Gerasa um 100 n. Chr. die Folge.

Fibonaccis Kaninchenmodell nimmt an: Jedes Kaninchenpaar bekommt pro Monat ein weiteres Paar, neugeborene Paare bekommen erst im zweiten Lebensmonat Nachwuchs, und die Tiere leben in einem abgeschlossenen Raum. Fibonacci begann mit einem trächtigen Paar, sodass im ersten Monat bereits 2 Paare gezählt werden. Für zwölf Monate gab er die Zahlen 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 an und erklärte das Bildungsgesetz als Summe zweier aufeinanderfolgender Glieder. Eine 2014 erschienene mathematisch-historische Analyse vertrat die Ansicht, der Hintergrund könne eher im Wissen von Bienenzüchtern in Bejaia über Bienenstammbäume liegen als im Kaninchenmodell.

In der Neuzeit zeigten Édouard Lucas und J. Wasteels, dass aufeinanderfolgende Fibonacci-Zahlen der Gleichung f_{n+1}^2 − f_{n+1} f_n − f_n^2 = (−1)^n genügen. Die Folge ist außerdem namensgebend für Datenstrukturen wie Fibonacci-Baum und Fibonacci-Heap. In Kunst und Unterhaltung wird sie häufig als besonderes Muster aufgegriffen, etwa in geometrischen Trugschlüssen, Literatur, Musik, Film, Videospielen und bildender Kunst; die mathematische Bedeutung steht dort meist nicht im Vordergrund.