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:
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.
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.
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.
- Zwischen Fibonacci-Folge und Goldenem Schnitt besteht eine Verwandtschaft. Je weiter man in der Folge fortschreitet, desto mehr nähert sich der Quotient aufeinanderfolgender Fibonacci-Zahlen dem Teilungsverhältnis des Goldenen Schnittes (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 .
Definition der Fibonacci-Folge Bearbeiten
Die Fibonacci-Folge ist durch das rekursive Bildungsgesetz
mit den Anfangswerten
definiert. Das bedeutet in Worten:
- Für die beiden ersten Zahlen wird der Wert vorgegeben.
- Jede weitere Zahl ist die Summe ihrer beiden Vorgänger in der Folge.
Daraus ergibt sich:
Aus der Forderung, dass die Rekursion
auch für ganze Zahlen gelten soll, erhält man eine eindeutige Fortsetzung auf den Index 0 und auf negative Indizes. Es gilt:
Die so erweiterte Fibonacci-Folge lautet dann
und heißt Folge der negaFibonacci-Zahlen.
Darüber hinaus ist eine Verallgemeinerung der Fibonacci-Zahlen auf komplexe Zahlen, proendliche Zahlen und auf Vektorräume möglich.
Eigenschaften Bearbeiten
Zu den zahlreichen bemerkenswerten Eigenschaften der Fibonacci-Zahlen gehört, dass sie dem Benfordschen Gesetz genügen.
Verwandtschaft mit dem Goldenen Schnitt Bearbeiten
Wie von Johannes Kepler festgestellt wurde, kommen die Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen dem Goldenen Schnitt
beliebig nahe. Dies folgt unmittelbar aus der Näherungsformel für große Zahlen :
Diese Quotienten zweier aufeinanderfolgender Fibonacci-Zahlen haben eine bemerkenswerte Kettenbruchdarstellung:
mit der -Notation aus dem Artikel Kettenbruch.
Da diese Quotienten gegen den Goldenen Schnitt konvergieren, lässt sich dieser als der unendliche periodische Kettenbruch:
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 und beliebige natürliche Zahlen annehmen.
Beziehungen zwischen den Folgengliedern Bearbeiten
- mit der Lucas-Folge (mit ), insbesondere:
- (Identität von Catalan)
- (Identität von Cassini, Spezialfall der Catalan-Identität)
- (Identität von d’Ocagne)
- Je zwei benachbarte Fibonaccizahlen sind teilerfremd, d. h. .
- ; für gilt auch die Umkehrung. Insbesondere kann für nur dann eine Primzahl sein, wenn eine Primzahl ist.
- (Genau jede dritte Fibonacci-Zahl ist durch 2 teilbar.)
- (Genau jede vierte Fibonacci-Zahl ist durch 3 teilbar.)
- (Genau jede sechste Fibonacci-Zahl ist durch 4 teilbar.)
- (Genau jede fünfte Fibonacci-Zahl ist durch 5 teilbar.)
- (Genau jede achte Fibonacci-Zahl ist durch 7 teilbar.)
- (Genau jede zwölfte Fibonacci-Zahl ist durch 16 teilbar.)
Summenformeln:
Es gibt noch zahlreiche weitere derartige Formeln.
Zeckendorf-Theorem Bearbeiten
Das nach Edouard Zeckendorf benannte Zeckendorf-Theorem besagt, dass jede natürliche Zahl eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen geschrieben werden kann. Das heißt, es gibt für jedes eine eindeutige Darstellung der Form
Die entstehende Folge von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Sehr eng hängt damit der Fibonacci-Kode zusammen.
Berechnung Bearbeiten
Formel von Moivre-Binet Bearbeiten
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.
Die Fibonacci-Zahlen lassen sich direkt mittels
berechnen, wobei die beiden Lösungen der charakteristischen Gleichung sind. Mit
gilt explizit:
Bemerkenswert ist das Zusammenspiel zweier irrationaler Zahlen und , das zu einem ganzzahligen Ergebnis führt. Die Abbildung zeigt die beiden Folgen und sowie als deren Differenz.
Näherungsformel für große Zahlen Bearbeiten
Der Einfluss von geht rasch gegen Null, bspw. ist . Das kann man verwenden, um die Berechnung abzukürzen, indem man den Term für genügend große ignoriert und das Ergebnis zur nächsten natürlichen Zahl rundet:
Tatsächlich geht das schon für .
Induktiver Beweis Bearbeiten
Einer der einfachsten Beweise gelingt induktiv. Wegen und ist der Induktionsanfang erfüllt. Angenommen, die Formel gelte für alle Werte von bis (starke Induktionsvoraussetzung). Wir zeigen, dass sie dann notwendigerweise auch für gilt:
Dabei haben wir benutzt, dass und der charakteristischen Gleichung genügen.
Nach dem Prinzip der vollständigen Induktion muss nun die Formel für alle gelten.
Herleitung über ein Eigenwertproblem Bearbeiten
Die Formel von Binet kann mit Matrizenrechnung und dem Eigenwertproblem in der linearen Algebra hergeleitet werden mittels folgendem Ansatz:
Nun transformiert man die Matrix in eine Diagonalmatrix durch Betrachtung als Eigenwertproblem.
Es gilt , wobei die Matrix der Eigenvektoren und die Diagonalmatrix mit den Eigenwerten ist. Damit folgt:
Herleitung mittels Differenzengleichung Bearbeiten
Eine andere Herleitungsmöglichkeit folgt aus der Theorie der linearen Differenzengleichungen:
Sei eine geometrische Folge, so ergibt sich:
Wenn also so gewählt wird, dass die charakteristische Gleichung erfüllt ist (also oder ), wird , d. h., erfüllt die Fibonacci-Rekursion mit dem Rekursionsanfang und .
Die durch , , rekursiv definierte Folge hat die explizite Darstellung . Ebenso , , .
Mit und genügt wegen der Superpositionseigenschaft auch jede Linearkombination der Fibonacci-Rekursion . Mit Hilfe eines linearen Gleichungssystems ergibt sich und , damit und . Folglich ergibt sich explizit .
Für ergibt sich und , d. h. die klassische Lucas-Folge mit explizit .
Herleitung mittels z-Transformation Bearbeiten
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.
Alternierende Näherung Bearbeiten
Die Quotienten aufeinanderfolgender Glieder der Fibonacci-Folge sind abwechselnd kleiner und größer als der Goldene Schnitt:
Herleitung |
Mithilfe der Formel von Moivre-Binet lässt sich eine einfach Herleitung angeben. Denn für die Zahlen der genannten Formel und natürliche gilt:
(1) , da im Doppelbruch der Darstellung der Folgeglieder mit Moivre-Binet der gemeinsame Nenner verschwindet. – Entsprechend:
(2) Die Ungleichungen (1) und (2) ergeben zusammen die Behauptung. |
Die Differenz dieser oberen und unteren Schranke von konvergiert für wachsende rasch gegen Null wegen
Bei der Vereinfachung des Zählers wurde die Identität von Cassini nebst verwendet.
Erzeugende Funktion Bearbeiten
Eine erzeugende Funktion der Fibonacci-Zahlen ist
Die auf der linken Seite stehende Potenzreihe konvergiert für . Über die angegebene Partialbruchzerlegung erhält man wieder die Formel von Moivre-Binet.
Herleitung der erzeugenden Funktion |
Für ist da da und Die Rekursionsbedingung induziert daher
ausklammern:
Nach Division durch das Polynom das nicht das Nullpolynom ist, folgt die angegebene Form. |
Mit einer geeigneten erzeugenden Funktion lässt sich ein Zusammenhang zwischen den Fibonacci-Zahlen und den Binomialkoeffizienten darstellen:
Wegen für und kann auch ohne Gaußklammern geschrieben werden:
Herleitung |
Die erzeugende Funktion kann auch geschrieben werden: (1) für dem Betrage nach hinreichend kleine gilt:
(2) Gleichsetzen ergibt: , wobei [] Gaußklammern sind. Bei der Umformung wurden der binomische Lehrsatz und die Umsummierung mit verwendet. Koeffizientenvergleich ergibt den angegebenen Zusammenhang. |
Die Schreibweise für die erzeugende Funktion erlaubt auch die Darstellung
Herleitung |
In der Darstellung von als unendliche Summe ist der Summand mit verzichtbar, siehe vorherige Herleitung. Die -te Ableitung der erzeugenden Funktion ist mit der Potenzregel:
Für verschwindet die Summe der letzten Zeile. Für dieses entsteht mit Division durch die Behauptung. |
Verbindung zum reziproken Wert der Zahl 89 Bearbeiten
Wertet man die erzeugende Funktion an der Stelle aus, so erhält man , folglich lässt sich in eine unendliche Summe von Fibonacci-Zahlen zur Basis zerlegen.
Darstellung mit Matrizen Bearbeiten
Die Fibonacci-Zahlen tauchen auch als Einträge der Potenzen der Matrix auf:
Aus der Relation ergibt sich beispielsweise die erste oben angegebene Formel für . 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 das -te Paar aus dem Startpaar . Dies und die Tatsache, dass die Eigenwerte von 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 Bearbeiten
Die Fibonacci-Zahlen können mithilfe des Pascalschen Dreiecks beschrieben werden. Um die -te Fibonacci-Zahl zu bestimmen, nimmt man aus der -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. , , usw. Anschließend addiert man diese gewichteten Elemente zusammen und dividiert durch .
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 cyan hervorgehoben.
Herleitung |
Ausgehend von der expliziten Formel für die Fibonacci-Zahlen (s. Formel von Moivre-Binet weiter oben in diesem Artikel) kann man zunächst den Term im Nenner ausklammern und die verbliebene Differenz mittels Binomialkoeffizienten ausschreiben und anschließend zusammenfassen: Für die Differenz unter dem Summenzeichen gilt: sodass man die Summe auf ungerade reduzieren kann: Der -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 -Termen überhaupt ganze Zahlen liefert. Die Abrundung in der Summen-Obergrenze ist übrigens notwendig, damit die Indizierung nicht über den Wert hinausgeht und die ursprüngliche Summenbegrenzung eingehalten wird. Vergleicht man die unter dem Summenzeichen verbliebenen Binomialkoeffizienten mit denen im Pascalschen Dreieck, erkennt man, dass es sich dabei um jeden zweiten Koeffizienten in der entsprechenden Zeile des Dreiecks handelt (wie es im Bild oben visualisiert ist). Man kann die Formel also auch als schreiben mit der Bezeichnung für einen Binomialkoeffizienten an der -ten Stelle in der -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 |
Reihen von Reziproken Bearbeiten
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 lässt sich mithilfe der Lambert-Reihe
- Die unendliche Summe der Kehrwerte der Fibonacci-Zahlen mit ungeradem Index lässt sich durch eine Jacobische Thetafunktion ausdrücken:
- Ebenfalls geschlossen lässt sich die Formel für die Summe darstellen, wenn der Nenner um 1 erhöht wird:
- Die unendliche Summe der Kehrwerte aller Fibonacci-Zahlen
- Die unendliche Summe der Kehrwerte der Quadrate der Fibonaccizahlen findet sich bei Borwein: