Formel von Binet

Erklärung

Die Fibonacci-Zahlen sind rekursiv definiert: $F_0 = 0$, $F_1 = 1$ und jede weitere Zahl ist die Summe der beiden vorherigen. Das ergibt $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ Die Formel von Binet liefert $F_n$ direkt, ohne alle Vorgänger zu berechnen.

Herleitung: Man sucht Lösungen der Form $F_n = x^n$. Einsetzen in $F_{n+1} = F_n + F_{n-1}$ ergibt die charakteristische Gleichung $x^2 = x + 1$ mit den Lösungen

Jede Kombination $c_1 \Phi^n + c_2 \psi^n$ erfüllt die Rekursion. Die Startwerte $F_0 = 0$ und $F_1 = 1$ legen $c_1 = \frac{1}{\sqrt{5}}$ und $c_2 = -\frac{1}{\sqrt{5}}$ fest. Die Formel lässt sich auch mit vollständiger Induktion beweisen.

Folgerungen:

• Wegen $|\psi| < 1$ wird der zweite Summand schnell winzig. Für alle $n \geq 0$ ist $F_n$ die nächste ganze Zahl an $\frac{\Phi^n}{\sqrt{5}}$.
• Die Fibonacci-Zahlen wachsen exponentiell, und der Quotient $\frac{F_{n+1}}{F_n}$ strebt gegen den goldenen Schnitt $\Phi$.

Beispiele

$F_{10}$:

$F_{20}$ mit der Rundungsformel: $\frac{\Phi^{20}}{\sqrt{5}} \approx 6765{,}00003$, also $F_{20} = 6765$.

Quotient: $\frac{F_{11}}{F_{10}} = \frac{89}{55} \approx 1{,}6182$, sehr nahe an $\Phi \approx 1{,}6180$.

Typische Fehler

• Den zweiten Summanden weglassen, ohne zu runden. $\frac{\Phi^n}{\sqrt{5}}$ ist nie exakt ganzzahlig. Ohne $\psi^n$ muss man auf die nächste ganze Zahl runden.
• Andere Startwerte verwenden. Beginnt die Folge mit $F_1 = F_2 = 1$, stimmt die Formel mit derselben Nummerierung. Wer aber $F_0 = 1$ setzt, verschiebt den Index um eins.
• Vorzeichen von $\psi$ übersehen. $\psi$ ist negativ, daher wechselt $\psi^n$ das Vorzeichen: Für gerade $n$ liegt $\frac{\Phi^n}{\sqrt{5}}$ etwas über $F_n$, für ungerade etwas darunter.