Fibonacci-Rechner

F(1) = 1, F(2) = 1, F(n) = F(n − 1) + F(n − 2) ⇒ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …; das Verhältnis benachbarter Glieder → φ = (1 + √5) / 2 = 1,6180339887…

F(1) = F(2) = 1

Die beiden Startwerte und die Entscheidung, die diese Seite ausdrücklich trifft. Ab 1 gezählt sind F(1) und F(2) beide 1 und F(10) ist 55. Die andere übliche Vereinbarung setzt F(0) = 0 und F(1) = 1, was jeden Index um eins verschiebt, sodass das fünfte Glied 5 ist statt 8. Keine von beiden ist falsch, aber sie sind sich über jeden einzelnen Index uneinig

F(n) = F(n − 1) + F(n − 2)

Die Rekursion, und sie ist die ganze Definition. Jedes Glied ist die Summe der beiden davor: 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8. Dass von zwei Startwerten aus vorwärts gearbeitet wird, ist der Grund, warum die Seite tausend Glieder so leicht erzeugt wie zehn — es gibt keine Formel zu lösen, nur eine Addition, die sich wiederholt

n

Wie viele Glieder Sie wollen, von 2 bis 78. Die untere Grenze ist 2 und nicht 1, weil die Verhältnisausgabe ein Glied und das davor braucht; ein einzelnes Glied hätte nichts, wodurch geteilt werden könnte, und die Seite lehnt es ab, statt ein leeres Verhältnis zu drucken. Die obere Grenze ist die Stelle, an der die Glieder in gewöhnlicher Gleitkomma-Arithmetik nicht mehr exakt sind

F(78) = 8944394323791464

Das letzte Glied, das diese Seite erreicht, und der Grund, warum dort Schluss ist. F(79) ist 14472334024676221 und liegt über der größten ganzen Zahl, die eine Zahl doppelter Genauigkeit exakt hält — 9007199254740991 —, ab da wären die gedruckten Ziffern also eine Näherung statt der Folge. Die Seite lehnt 79 ab, statt ein fast richtiges Glied zu drucken

F(n) / F(n − 1)

Die Verhältnisausgabe. Sie ist nicht der Goldene Schnitt, und die Seite behauptet es auch nicht: 1,6667 kommt beim fünften Glied heraus und liegt weit von 1,618 entfernt. Was sie ist, ist eine Schätzung, die schnell besser wird — das zwanzigste Glied stimmt bereits auf acht Nachkommastellen, und das ist genau die Genauigkeit, die die Seite druckt

φ = 1,6180339887…

Der Goldene Schnitt, die Zahl, gegen die diese Verhältnisse laufen. Sie ist die positive Lösung von x² = x + 1, und das ist dieselbe Rekursion als Gleichung — kein Zufall, sondern der Grund, warum die Fibonacci-Verhältnisse dort landen. Beachten Sie, dass die gedruckte Schätzung höchstens 1,61803399 ist: Die Seite zeigt acht Nachkommastellen, und die echte Zahl geht darüber hinaus

Ein Glied nachzuschlagen ist der schlichte Nutzen: Ein Rätsel fragt nach dem zehnten Glied, oder eine Folge in einem Buch geht weiter, als Sie von Hand addieren möchten, und die Seite liefert den Wert und den Lauf der Glieder dorthin. Die Verhältnisausgabe bedient eine andere Frage, nämlich die, woher der Goldene Schnitt kommt. Zu sehen, wie 2, 1,5, 1,6667, 1,6, 1,625, 1,615 sich auf 1,618 einpendeln, ist ein viel kürzerer Weg zum Verständnis dieses Zusammenhangs als ein Beweis, und die Referenztabelle auf dieser Seite ist genau für diese Lesart angelegt. Ein dritter Nutzen liegt im Programmieren und im Studium, wo die Rekursion das Standardbeispiel für Rekursion überhaupt ist und die Folge das Standardbeispiel für eine rekursive Definition, die iterativ viel billiger zu berechnen ist — die Schleife dieser Seite ist die iterative Fassung, und deshalb kosten 78 Glieder gar nichts. Die Zahlen tauchen außerdem in Schätzaufgaben auf, in denen Wachstum sich selbst verstärkt: die Anzahl der Möglichkeiten, einen Streifen mit Quadraten und Dominosteinen zu pflastern, die Anzahl der Wege eine Treppe hinauf in Ein- oder Zweierschritten, und die Verzweigungszahlen einer Pflanze, die sich jede Saison teilt, folgen derselben Rekursion. Wenn die Frage auf das Verhältnis zielt und nicht auf die Folge, behandelt der Goldener-Schnitt-Rechner es als eigene Zahl mit eigenen Eigenschaften; auch die goldene Spirale, die sich aus den Quadraten der Glieder zeichnen lässt, gehört dorthin. Wenn es um das Wachstumsmuster geht, deckt der Rechner für exponentielles Wachstum die glatte Fassung dessen ab, was diese Glieder in Sprüngen annähern.

1. Die ersten zehn Glieder: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

   1. Beginnen Sie mit 1 und 1, den beiden Startwerten dieser Seite
   2. 1 + 1 = 2, dann 1 + 2 = 3, dann 2 + 3 = 5, dann 3 + 5 = 8
   3. Weiter: 5 + 8 = 13, 8 + 13 = 21, 13 + 21 = 34, 21 + 34 = 55
   4. Zehn Glieder, das zehnte ist also 55; das Verhältnis der letzten beiden ist 55 ÷ 34 = 1,61764706

   Die Standardeingabe. Beachten Sie, dass das zehnte Glied 55 ist und das Verhältnis von 55 zu 34 den Wert 1,61764706 hat — nah am Goldenen Schnitt, aber in der dritten Nachkommastelle noch sichtbar davon entfernt. Genau das macht die Folge sehenswert statt bloß nachschlagbar: Die Konvergenz ist schnell, aber sie ist nicht augenblicklich, und zehn Glieder reichen noch nicht, damit die gedruckten acht Nachkommastellen 1,61803399 erreichen.

2. Der kürzeste Lauf: zwei Glieder

   1. Zwei Glieder sind die kleinste Anforderung, die diese Seite annimmt
   2. Die Folge besteht nur aus den beiden Startwerten: 1 und 1
   3. Das zweite Glied ist 1, die Ausgabe für das n-te Glied ist also 1
   4. Das Verhältnis ist 1 ÷ 1 = 1 — so weit vom Goldenen Schnitt entfernt, wie diese Seite je kommt

   Die untere Grenze und der Grund, warum sie bei 2 liegt und nicht bei 1. Die Verhältnisausgabe braucht überhaupt erst zwei Glieder; mit einem einzigen gäbe es nichts, wodurch geteilt werden könnte, deshalb lehnt die Seite die 1 ab, statt ein leeres Feld oder eine Null zu drucken. Das Verhältnis 1 ist außerdem der Ausgangspunkt der ganzen Konvergenz: Jedes spätere Verhältnis ist ein Schritt davon weg, und der Weg von 1 nach 1,618 ist das, was die Tabelle unten Glied für Glied ausbreitet.

3. Wo das Verhältnis zur Ruhe kommt: zwanzig Glieder

   1. Führen Sie die Rekursion vom zehnten Glied aus weiter: 34 + 55 = 89, 55 + 89 = 144 und so fort
   2. Das zwanzigste Glied ist 6.765, das neunzehnte ist 4.181
   3. 6.765 ÷ 4.181 = 1,61803396317…
   4. Auf die acht Nachkommastellen gerundet, die die Seite druckt, ist das 1,61803396

   Zwanzig Glieder genügen. Der echte Goldene Schnitt beginnt mit 1,6180339887, und die Schätzung hier stimmt damit auf sieben Nachkommastellen überein — die Abweichung liegt jetzt in der achten, und das ist die letzte, die gedruckt wird. Vergleichen Sie das mit den zehn Gliedern, wo der Fehler schon in der dritten Nachkommastelle sichtbar war. Das ist der Punkt, um den es dieser Seite geht: Die Rekursion hat in ihrer Definition nichts mit dem Goldenen Schnitt zu tun, und trotzdem erzeugt sie ihn — schnell und aus nichts als Addition.

Die Anzahl der Glieder muss eine ganze Zahl von 2 bis 78 sein. Die 1 wird abgelehnt, weil die Verhältnisausgabe zwei Glieder braucht, und die 79 wird abgelehnt, weil die Glieder dort nicht mehr exakt sind: F(78) ist 8944394323791464 und damit die letzte Fibonacci-Zahl, die genau in eine Zahl doppelter Genauigkeit passt, und F(79) liegt über der Grenze von 9007199254740991. Die Seite lehnt die Anfrage ab, statt ein genähertes Glied zurückzugeben, denn eine Zahl, die fast richtig ist, aber auf sechzehn Stellen gedruckt wird, sieht genauso aus wie eine richtige. Die Zählung beginnt bei 1, und diese Seite verwendet F(1) = F(2) = 1. Die andere weit verbreitete Vereinbarung setzt F(0) = 0 und F(1) = 1 und verschiebt damit jeden Index um eins — unter ihr ist das fünfte Glied 5, hier ist es 8. Beide Vereinbarungen sind in Lehrbüchern und in Software in Gebrauch; wenn Sie diese Seite also gegen eine andere Quelle halten und die Zahlen um eine Position versetzt sind, liegt das daran und nicht an einem Fehler. Die Verhältnisausgabe ist eine Schätzung und wird auf acht Nachkommastellen gedruckt; für keine endliche Anzahl von Gliedern ist sie genau der Goldene Schnitt, wobei beim achtundsiebzigsten die gedruckten acht Ziffern mit ihm übereinstimmen. Die Glieder selbst werden als durch Kommas getrennte Liste ohne Gruppierung gedruckt, das zehnte Glied liest sich also 55 und das achtundsiebzigste 8944394323791464 — lange Glieder laut vorzulesen ist eine Aufgabe für die Ausgabe des n-ten Glieds und nicht für die Liste. Die Referenztabelle schließlich steht fest bei den ersten zehn Gliedern und folgt Ihrer Eingabe nicht; sie ist dazu da, das Einpendeln des Verhältnisses zu zeigen, und nicht, um zu beantworten, was Sie eingetippt haben.

Beginnt die Folge bei F(0) oder bei F(1)?

Diese Seite beginnt bei F(1), also F(1) = 1, F(2) = 1, F(3) = 2, und das zehnte Glied ist 55. Die andere weit verbreitete Vereinbarung setzt F(0) = 0 und F(1) = 1, was jeden Index um eins verschiebt — unter ihr ist das fünfte Glied 5, hier ist es 8. Beide sind in Lehrbüchern und in Software üblich, und keine ist ein Fehler. Wenn Sie diese Seite aber gegen eine andere Quelle halten und die Werte um eine Position versetzt sind, liegt es daran; es ist der häufigste Weg, ein Fibonacci-Ergebnis falsch zu beantworten.

Warum ändert sich das Verhältnis ständig, statt sich sofort einzupendeln?

Weil es ein Grenzwert ist und keine Identität. Jedes Glied ist die Summe der beiden davor, das Verhältnis aufeinanderfolgender Glieder bewegt sich also nach einer eigenen festen Regel, und diese Bewegung wechselt oberhalb und unterhalb des Ziels ab, mit jedem Ausschlag etwa halb so groß wie beim Mal davor. Die Tabelle auf dieser Seite zeigt es: 2, 1,5, 2, 1,667, 1,6, 1,625, dann enger werdend 1,615 und 1,619. Zehn Glieder sind nah dran, zwanzig reichen für die acht Nachkommastellen, die die Seite druckt, und für keine endliche Anzahl von Gliedern ist das Verhältnis genau der Goldene Schnitt — nur immer näher dran.

Was ist der Goldene Schnitt, und warum erzeugt diese Folge ihn?

Der Goldene Schnitt ist 1,6180339887…, die positive Lösung von x² = x + 1. Diese Gleichung ist die Fibonacci-Rekursion in anderer Schreibweise — wenn die Verhältnisse sich auf irgendeine Zahl einpendeln, muss diese Zahl sie erfüllen —, und deshalb landet die Folge dort und deshalb ist die Konvergenz kein Zufall und keine Kuriosität. Das Verhältnis ist außerdem die Zahl, die sich am schwersten durch Brüche annähern lässt, weil ihr Kettenbruch nur Einsen enthält; genau diese Eigenschaft nutzen Pflanzen, wenn sie Blätter und Samen danach anordnen.

Warum kann ich nur 78 Glieder anfordern?

Weil F(79) größer ist als die größte ganze Zahl, die eine Zahl doppelter Genauigkeit exakt halten kann, nämlich 9007199254740991. F(78) ist 8944394323791464 und damit exakt; F(79) ist 14472334024676221 und würde als etwas Knapp-Danebenliegendes gespeichert. Die Seite lehnt die Anfrage ab, statt eine Näherung zu drucken, denn ein Glied, das auf sechzehn Stellen gedruckt wird, sieht genauso aus wie ein richtiges — der Fehler ist der Ausgabe nicht anzusehen. Die Gliedzahl ist eine Tatsache der Gleitkomma-Arithmetik und keine der Mathematik; die Folge selbst geht immer weiter.

Wo kommt die Kaninchenaufgabe ins Spiel?

Fibonacci hat die Folge mit einem Rätsel eingeführt: Man beginnt mit einem Paar Kaninchen, lässt jedes Paar einen Monat reifen und danach jeden Monat ein neues Paar werfen, und zählt zu Beginn jedes Monats die Paare. Die Zahlen kommen als 1, 1, 2, 3, 5, 8 und so weiter heraus, weil die reifen Paare des Vormonats alle noch da sind und die neuen Paare von denen stammen, die einen Monat zuvor reif waren — das ist die Rekursion, nur aus einer völlig anderen Richtung hergeleitet. Es lohnt sich, das zu wissen, weil es zeigt, dass die Folge nicht durch eine einzige Anwendung definiert ist.

Kann ich das n-te Glied berechnen, ohne alle davor aufzulisten?

Grundsätzlich ja, und die Ausgabe für das n-te Glied gibt Ihnen diese Zahl auf einer eigenen Zeile, sie entsteht aber aus derselben Schleife und nicht aus einer Abkürzungsformel. Der Grund ist die Exaktheit: Es gibt eine geschlossene Form, die Formel von Binet, die die n-te Fibonacci-Zahl direkt aus dem Goldenen Schnitt liefert, doch darin werden irrationale Zahlen potenziert, und in Gleitkomma-Arithmetik driftet sie für größere n vom echten ganzzahligen Wert weg. Ganze Zahlen zu addieren ist exakt, wo jene Formel es nicht ist, also addiert die Seite. Dass von zwei Startwerten aus vorwärts gerechnet wird, ist auch der Grund, warum 78 Glieder gar nichts kosten — es gibt keine Formel zu lösen, nur eine Addition, die sich 76-mal wiederholt.

• Fibonacci Number — from Wolfram MathWorld (English original; die Rekursion, die geschlossene Form über den Goldenen Schnitt und die Identität, die das Verhältnis dorthin laufen lässt) — Wolfram MathWorld (United States)
• Golden Ratio — from Wolfram MathWorld (English original; die Zahl 1,6180339887…, ihre Definition als positive Lösung von x² = x + 1 und warum sie sich am schwersten durch Brüche annähern lässt) — Wolfram MathWorld (United States)
• Fibonacci — from Wolfram MathWorld (English original; die Folge als eigener Eintrag, mit ihren Gliedern und ihren Eigenschaften) — Wolfram MathWorld (United States)
• Dezimalbruch — Mathebibel: die Dezimaldarstellung einer Zahl, also was es heißt, wenn ein Verhältnis wie 1,6180339887… nicht abbricht und auf acht Stellen gerundet wird — Mathebibel (Deutschland)