In dieser Blog-Folge zeige ich Dir, wie Du mit den gelernten Techniken die bekannte Formel von Moivre-Binet zur expliziten Darstellung der Fibonacci-Zahlen herleiten kannst.
In der vorigen Blog-Folge haben wir gesehen, wie wir mithilfe von Potenzreihen für eine rekursiv definierten Folge eine explizite Formel für die Folgenglieder herleiten können. Die bekannteste rekursiv definierte Folge ist die Fibonacci-Folge. Wenn unsere Technik zur Herleitung einer expliziten Formel auch für die Fibonacci-Folge funktioniert, dann müssten wir so die bekannte explizite Formel für die Fibonacci-Zahlen, die Formel von Moivre-Binet, herleiten können. In dieser Blog-Folge zeige ich Dir genau diese Herleitung.
Zur Erinnerung: Die Folgenglieder der Fibonacci-Folge $(F_n)_{n\in\N_0}$ sind definiert durch \[ F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} \text{ für } n \geq 2. \] Zur Herleitung der Formel von Moivre-Binet nutzen wir wieder unser vierschrittiges Schema.
Schritt 1
Wir stellen die Potenzreihe \[ \sum_{n=0}^\infty F_n z^n \] auf und zeigen, dass sie einen positiven Konvergenzradius hat. Wir können wieder leicht durch Anwendung von Induktion zeigen, dass die Folgenglieder $F_n$ alle nicht negativ sind und dass die Folge monoton wachsend ist. Das Quotientenkriterium liefert uns dann \[ \left| \frac{F_{n+1}z^{n+1}}{F_nz^n}\right| = \frac{F_n + F_{n-1}}{F_n}|z| \leq \frac{F_n+F_n}{F_n} |z| = 2|z|. \] Also ist die Potenzreihe für alle $z$ mit $|z| < \frac{1}{2}$ konvergent, der Potenzradius beträgt mindestens $\frac{1}{2}$.
Schritt 2
Wir definieren die erzeugenden Funktion \[ G(z) = \sum_{n=0}^\infty F_n z^n \] und leiten eine explizite Darstellung für $G(z)$ her. Es gilt \begin{eqnarray*} G(z) = \sum_{n=0}^\infty F_n z^n & = & 0 + z + \sum_{n=2}^\infty F_n z^n \\ & = & z + \sum_{n=2}^\infty (F_{n-1} + F_{n-2}) z^n \\ & = & z + \sum_{n=2}^\infty F_{n-1} z^n + \sum_{n=2}^\infty F_{n-2} z^n \\ & = & z + z\sum_{n=1}^\infty F_{n-1} z^{n-1} + z^2 \sum_{n=2}^\infty F_{n-2} z^{n-2} \\ & = & z + z \sum_{n=0}^\infty F_n z^n + z^2 \sum_{n=0}^\infty F_n z^n \\ & = & z + zG(z) + z^2G(z). \end{eqnarray*} Damit folgt \begin{eqnarray*} & & G(z) = z + zG(z) + z^2G(z) \\ & \Rightarrow & G(z) - zG(z) -z^2G(z) = z \\ & \Rightarrow & G(z)(1-z-z^2) = z \\ & \Rightarrow & G(z) = \frac{z}{1-z-z^2}. \end{eqnarray*}
Schritt 3
Wir führen eine Partialbruchzerlegung durch. Es gilt \[ G(z) = \frac{z}{1-z-z^2} = \frac{-z}{z^2 + z -1}. \] Die Nullstellen des Nennerpolynoms sind \[ \lambda_{1,2} := -\frac{1}{2} \pm \sqrt{\frac{1}{4}+1} = \frac{-1\pm\sqrt{5}}{2}. \]
An dieser Stelle verwenden wir nun einen kleinen Trick. Wir rechnen nicht mit den konkreten Werten für $\lambda_{1,2}$ weiter, sondern verwenden stattdessen durchgehend in unserer Rechnung die Konstanten $\lambda_1$ und $\lambda_2$. Erst ganz am Ende, wenn wir eine explizite Formel haben, in der dann natürlich zunächst noch $\lambda_{1,2}$ auftreten, setzen wir die konkreten Werte für $\lambda_{1,2}$ ein. Wir tun dies, um nicht permanent mit den Wurzeltermen rechnen zu müssen. Hierdurch wird die Rechnung einfacher und weniger fehleranfällig.
Also gilt $z^2 + z -1 = (z-\lambda_1)(z-\lambda_2)$ und \[ G(z) = \frac{-z}{z^2 + z -1} = \frac{A}{z-\lambda_1} + \frac{B}{z-\lambda_2} \] mit noch unbekannten Zahlen $A,B \in \R$, die wir nun bestimmen. \begin{eqnarray*} \frac{-z}{z^2 + z -1} & = & \frac{A}{z-\lambda_1} + \frac{B}{z-\lambda_2} \\ & = & \frac{A(z-\lambda_2)+B(z-\lambda_1)}{(z-\lambda_1)(z-\lambda_2)} \\ & = & \frac{(A+B)z + (-\lambda_2 A =\lambda_1 B)}{z^2+z-1} \end{eqnarray*} Ein Koeffizientenvergleich ergibt das lineare Gleichungssystem \[ \begin{array}{rcrcr} A & + & B & = & -1 \\ -\lambda_2 A & - & \lambda_1 B & = & 0. \end{array} \] Wenn wir die erste Gleichung mit $\lambda_1$ multiplizieren, erhalten wir \[ \begin{array}{rcrcr} \lambda_1 A & + & \lambda_ 1 B & = & -\lambda_1 \\ -\lambda_2 A & - & \lambda_1 B & = & 0. \end{array} \] Eine Addition der beiden Gleichungen liefert \[ \lambda_1 A - \lambda_2 A = -\lambda_1 \] und somit \[ A = \frac{-\lambda_1}{\lambda_1 - \lambda_2}. \] Setzen wir die Lösung für $A$ in die Gleichung $A+B=-1$ ein, erhalten wir \[ B = -1 - \frac{-\lambda_1}{\lambda_1 - \lambda_2} = \frac{(-1)(\lambda_1-\lambda_2) + \lambda_1}{\lambda_1 - \lambda_2} = \frac{\lambda_2}{\lambda_1 - \lambda_2}. \] Also gilt \[ G(z) = \frac{-\frac{\lambda_1}{\lambda_1-\lambda_2}}{z-\lambda_1} + \frac{\frac{\lambda_2}{\lambda_1-\lambda_2}}{z-\lambda_2}. \] Nun gilt \[ \frac{-\frac{\lambda_1}{\lambda_1-\lambda_2}}{z-\lambda_1} = \frac{1}{\lambda_1 - \lambda_2} \cdot \frac{1}{1-\frac{z}{\lambda_1}} \] und \[ \frac{\frac{\lambda_2}{\lambda_1-\lambda_2}}{z-\lambda_2} = - \frac{1}{\lambda_1 - \lambda_2} \cdot \frac{1}{1-\frac{z}{\lambda_2}}. \] Weiterhin gilt (geometrische Reihe!) \[ \frac{1}{1-\frac{z}{\lambda_1}} = \sum_{n=0}^\infty \left(\frac{z}{\lambda_1}\right)^n = \sum_{n=0}^\infty \left(\frac{1}{\lambda_1}\right)^n z^n \] und \[ \frac{1}{1-\frac{z}{\lambda_2}} = \sum_{n=0}^\infty \left(\frac{1}{\lambda_2}\right)^n z^n. \] Damit ist $G(z)$ eine Linearkombination bekannter Potenzreihen.
Schritt 4
Mit den Ergebnissen aus Schritt 3 erhalten wir \begin{eqnarray*} \sum_{n=0}^\infty F_n z^n = G(z) & = & \frac{1}{\lambda_1 - \lambda_2} \left(\frac{1}{1-\frac{z}{\lambda_1}} - \frac{1}{1-\frac{z}{\lambda_2}}\right) \\ & = & \frac{1}{\lambda_1 - \lambda_2} \left( \sum_{n=0}^\infty \left(\frac{1}{\lambda_1}\right)^n z^n - \sum_{n=0}^\infty \left(\frac{1}{\lambda_2}\right)^n z^n \right) \\ & = & \frac{1}{\lambda_1 - \lambda_2} \sum_{n=0}^\infty \left( \left(\frac{1}{\lambda_1}\right)^n - \left(\frac{1}{\lambda_2}\right)^n \right) z^n. \end{eqnarray*} Daraus ergibt sich mit dem Identitätssatz für Potenzreihen die explizite Formel \[ F_n = \frac{1}{\lambda_1 - \lambda_2} \left( \left(\frac{1}{\lambda_1}\right)^n - \left(\frac{1}{\lambda_2}\right)^n \right). \] für die $n$-te Fibonacci-Zahl.
An dieser Stelle setzen wir nun für $\lambda_{1,2}$ wieder die konkreten Werte ein. Wir erhalten \[ \frac{1}{\lambda_1 - \lambda_2} = \frac{1}{\frac{-1+\sqrt{5}}{2}-\frac{-1-\sqrt{5}}{2}} = \frac{1}{\sqrt{5}} \] sowie \[ \frac{1}{\lambda_1} = \frac{2}{-1+\sqrt{5}} = \frac{2(-1-\sqrt{5})}{(-1+\sqrt{5})(-1-\sqrt{5})} = \frac{2(-1-\sqrt{5})}{-4} = \frac{1+\sqrt{5}}{2} \] und auf analoge Weise \[ \frac{1}{\lambda_2} = \frac{1-\sqrt{5}}{2}. \] Also gilt \[ F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right). \] Dies ist die bekannte Formel von Moivre-Binet für die Fibonacci-Zahlen.
Teilen und Drucken