mini|hochkant=1.15|Kachelmuster aus Quadraten, deren Kantenlängen der Fibonacci-Folge entsprechen mini|hochkant=1.15|Angenäherte Goldene Spirale, konstruiert mit Viertelkreisen. Das Verhältnis der aufeinander folgenden Radien ist das der aufeinander folgenden Fibonacci-Zahlen (Φ bei der Goldenen Spirale).
Die Fibonacci-Folge ist die unendliche Folge natürlicher Zahlen, die mit zweimal der Zahl 1 beginnt und bei der jede weitere Zahl die Summe der beiden ihr vorangehenden Zahlen ist. In moderner Schreibweise wird diese Folge zusätzlich mit einer führenden Zahl 0 versehen: {| | links|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.
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. 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 mini|hochkant=1.4|Die ersten Folgenglieder der Fibonacci-Folge
Die Fibonacci-Folge ist durch das rekursive Bildungsgesetz für mit den Anfangswerten
definiert.Obwohl viele der Aussagen weiter unten auch gelten, wenn die Indizes (Subskripte) um einen festen Betrag verschoben werden, hat sich diese Festlegung eingebürgert. Sie hat auch den Vorteil, dass die Ergänzung auf negative Indizes sich symmetrisch zur 0 verhält. 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: {| class="wikitable" style="text-align:right; border:0" ! n || fn || rowspan="11" class="hintergrundfarbe-basis" style="border:0; | ! n || fn || rowspan="11" class="hintergrundfarbe-basis" style="border:0;" | ! n || fn || rowspan="11" class="hintergrundfarbe-basis" style="border:0;" | ! n || fn || rowspan="11" class="hintergrundfarbe-basis" style="border:0;" | ! n || fn || rowspan="11" class="hintergrundfarbe-basis" style="border:0;" | |- | 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
Stellt man die Definition um, so erhält man , was als (rückwärts-)rekursive Bildungsvorschrift die eindeutige Fortsetzung auf den Index 0 und negative Indizes erlaubt.
Man erhält: , , … bzw. allgemeiner für alle wie auch
Setzt man diese allgemeine Formel in (rückwärts-)rekursive Bildungsvorschrift ein, erhält man
Teilt man die Gleichung durch , erhält man
Die so erweiterte Fibonacci-Folge lautet dann +34 −21 +13 −8 +5 −3 +2 −1 +1 0 1 1 2 3 5 8 13 21 34 und heißt Folge der negaFibonacci-Zahlen.
Darüber hinaus ist eine Verallgemeinerung der Fibonacci-Zahlen auf komplexe Zahlen, proendliche ZahlenHendrik Lenstra: Profinite Fibonacci numbers. (PDF; 351 kB). und auf Vektorräume möglich.
Eigenschaften Zu den zahlreichen bemerkenswerten Eigenschaften der Fibonacci-Zahlen gehört, dass sie dem Benfordschen Gesetz genügen.Yvonne Stry, Rainer Schwenkert: Kapitel 11 Wahrscheinlichkeitsrechnung und Statistik, Abschnitt 6 Anwendungen. Eine sonderbare Ziffern-Verteilung und die Steuerrevision, Unterabschnitt 11.6.1, in: Mathematik kompakt für Ingenieure und Informatiker, Springer-Verlag, 2006, ISBN 978-3-540-32312-9.
Näherung an den Goldenen Schnitt 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 Fibonacci-Folgen, bei denen und beliebige natürliche Zahlen annehmen.
Beziehungen zwischen den Folgengliedern Identitäten
mit der Lucas-Folge (mit ), insbesondere:
(Identität von Catalan) (Identität von Cassini, Spezialfall der Catalan-Identität) (Identität von d’Ocagne)
Teilbarkeit
Je zwei benachbarte Fibonacci-Zahlen sind teilerfremd, d. h. .Bei der Berechnung dieses größten gemeinsamen Teilers mit dem euklidischen Algorithmus tritt der ungünstigste Fall ein in Bezug auf die Anzahl der benötigten Divisionen mit Rest. Siehe dazu z. B. ; 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.) Für die Teilbarkeit durch Primzahlen gilt unter Verwendung des Jacobi-Symbols:
Summenformeln
Summenformel für negative Indizes:
Es gibt noch zahlreiche weitere derartige Formeln.
Reziproke Die Gleichung muss Landau (1899) bekannt gewesen sein, s. Borwein, Page 95, Exercise 3b.Wegen ergibt eine Multiplikation mit allen Nennern die Gleichung
die leicht verifiziert ist.
Zeckendorf-Theorem
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 mit und für alle .
Die entstehende Folge von Nullen und Einsen wird Zeckendorf-Sequenz genannt. Sehr eng hängt damit der Fibonacci-Kode zusammen.
Berechnung Formel von Moivre-Binet 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.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 3-540-42032-0, S. 12 ()). 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 978-3-8274-2349-8, S. 46 ()) oder Ben-Menahem (Ari Ben-Menahem: Historical Encyclopedia of Natural and Mathematical Sciences. Band 1. Springer, 2009, ISBN 978-3-540-68831-0, S. 611 ()).
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.
Näherungsformel für große Zahlen Der Einfluss von geht rasch gegen Null, bspw. ist . Das kann man verwenden, um die Berechnung abzukürzen, indem man die kleine Zahl einfach weglässt und das noch verbleibende kaufmännisch zur nächstgelegenen ganzen Zahl rundet. Mit Hilfe der Gaußschen Abrundungsfunktion lässt sich das so formalisieren: für alle
Induktiver Beweis 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). Dann gilt sie notwendigerweise auch für :
Dabei wird 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 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 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 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 Die Quotienten aufeinanderfolgender Glieder der Fibonacci-Folge sind abwechselnd kleiner und größer als der Goldene Schnitt:Gleichung (2.12) in: Fibonacci numbers and matrices. 15. Juni 2009, Robert C. Johnson, Department of Mathematical Sciences, Durham University, UK.
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 Eine erzeugende Funktion der Fibonacci-Zahlen ist