Folgen müssen nicht explizit definiert sein, sondern können auch rekurisv definiert werden. In der vorangegangenen Blogfolge haben wir bereits ein Beispiel hierfür gesehen. Die bekannteste rekursiv definierte Folge ist die Fibonacci-Folge.
Folgen müssen nicht explizit definiert sein, sondern können auch rekurisv definiert werden. Im vorangegangenen Blog haben wir bereits ein Beispiel hierfür gesehen. Die wohl bekannteste rekursiv definierte Folge ist die Fibonacci-Folge.
Definition
Die Fibonacci-Folge $(F_n)_{n\geq 0}$ ist wie folgt definiert: \begin{eqnarray*} F_0 & = & 0 \\ F_1 & = & 1 \\ F_n & = & F_{n-1} + F_{n-2} \text{ für } n \geq 2. \end{eqnarray*} Die in der Fibonacci-Folge auftretenden Zahlen $F_n$ heißen Fibonacci-Zahlen.Die nachfolgende Tabelle listet die Fibonacci-Zahlen bis $n=10$ auf: \[ \begin{array}{r|rrrrrrrrrrr} n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline F_n & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 \end{array} \] Anhand der Tabelle sehen wir sehr schön die durch die Rekursionsvorschrift gegebene Eigenschaft der Fibonacci-Zahlen: Ab $n=2$ ist jede Fibonacci-Zahl die Summe ihrer beiden Vorgänger.
Benannt ist die Fibonacci-Folge nach dem italienischem Mathematiker Leonardo Fibonacci. Er stellte diese berühmte Folge auf, als er das Wachstumsverhalten einer Kaninchenpopulation untersuchte. Auch viele andere Wachstumsvorgänge in der Natur können mithilfe der Fibonacci-Folge beschrieben werden. Das folgende Beispiel zeigt solch einen Wachstumsvorgang.
Beispiel
Wir haben Fliesen der Größe $1 \times 2$ und wollen damit einen Weg der Größe $n \times 2$ pflastern, also einen Weg mit Breite $2$ und Länge $n$. Die Fliesen können wir sowohl vertikal als auch horizontal verlegen. Wie viele Möglichkeiten gibt es, solch einen Weg zu pflastern?
Es sei $p_n$ die Anzahl der verschiedenen Pflasterungen für einen Weg der Größe $n \times 2$. Um die Frage zu beantworten müssen wir eine Formel für $p_n$ herleiten. Dazu bietet es sich an, dieses Problem zunächst für kleine $n$ zu betrachten.
Für $n=1$ gibt es nur eine Möglichkeit den Weg zu pflastern: Wir legen die Fliese in vertikaler Ausrichtung.
Also gilt $p_1 = 1$.Für $n=2$ gibt es zwei verschiedene Pflasterungen: Wir legen nebeneinander zwei Fliesen entweder horizontal oder vertikal ausgerichtet.
Somit ergibt sich $p_2 = 2$.Für $n=3$ können wir entweder mit einer vertikalen Fliese oder zwei horizontalen Fliesen beginnen. Im ersten Fall stehen uns nach der vertikalen Fliese die Möglichkeiten von $n=2$ zur Verfügung, im zweiten Fall die von $n=1$.
Also $p_3 = p_2 + p_1 = 3$.
Den Ansatz von $n=3$ können wir verallgemeinern. Wenn wir eine Pflasterung der Länge $n$ mit einer vertikalen Fliese beginnen, müssen wir anschließen noch die Länge $n-1$ pflastern, wozu wir $p_{n-1}$ Möglichkeiten haben. Legen wir dagegen als erstes zwei horizontale Fliesen, bleibt ein Restweg der Länge $n-2$, den wir auf $p_{n-2}$ verschiedene Weisen pflastern können. Damit ergibt sich $p_n = p_{n-1} + p_{n-2}$ für $n\geq 3$ und somit die gleiche Rekursionsvorschrift wie bei der Fibonacci-Folge.
Wir vergleichen die Zahlen $F_n$ und $p_n$ ab $n=1$: \[ \begin{array}{r|rrrrrrrr} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline F_n & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 \\ \hline p_n & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \end{array} \] Wir erkennen, dass die Folge $(p_n)$ der Fibonacci-Folge gleicht, allerdings im Index um eins verschoben.
Also gilt \[ p_n = F_{n+1}. \] Die Anzahl der Pflasterungen für einen Weg der Länge $n$ ist somit gleich der $n+1$-ten Fibonacci-Zahl.
Anhand der rekursiven Definition der Fibonacci-Zahlen können wir nur schwer das Wachstumsverhalten der Fibonacci-Folge einschätzen. Hierfür wäre eine explizite Formel für die Fibonacci-Zahlen besser. Glücklicherweise liefert uns die Formel von Moivre-Binet solch eine explizite Charakterisierung.
Satz (Formel von Moivre-Binet)
Für die Fibonacci-Folge $(F_n)_{n\in\mathbb{N}_0}$ 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). \]
Die Zahl \[ \frac{1+\sqrt{5}}{2} \approx 1.6180339887498948482 \] ist der sogenannte Goldene Schnitt. Sie beschreibt ein Größenverhältnis, das in der Natur immer wieder auftritt. Da \[ \frac{1-\sqrt{5}}{2} \approx -0.6180339887498948482 \] betraglich zwischen $0$ und $1$ liegt, wird der Term $\left( \frac{1-\sqrt{5}}{2} \right)^n$ für wachsendes $n$ betraglich immer kleiner und nähert sich der Null. Also gilt \[ F_n \approx \frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n, \] was bedeutet, dass die Fibonacci-Zahlen ein exponentielles Wachstum aufweisen.
Der Beweis der Formel von Moivre-Binet ist eine gute Übung zur vollständigen Induktion und zur Anwendung von Termumformungen. Ich empfehle, den Beweis einmal selbst durchzuführen.
Übung 1
Beweise die Formel von Moivre-Binet!
Für den Beweis nutzen wir vollständige Induktion. Da die rekursive Definition für die Fibonacci-Zahlen erst ab $n=2$ gilt, müssen wir als Induktionsanfang sowohl für $n=0$ als auch für $n=1$ zeigen, dass die Formel von Moivre-Binet korrekt ist.
$n=0$: \[ \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^0 - \left( \frac{1-\sqrt{5}}{2} \right)^0 \right) = \frac{1}{\sqrt{5}} (1-1) = 0 = F_0 \]
$n=1$: \[ \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^1 - \left( \frac{1-\sqrt{5}}{2} \right)^1 \right) = \frac{1}{\sqrt{5}} \cdot \frac{2\sqrt{5}}{2} = 1 = F_1 \]
$n \rightarrow n+1$: \begin{eqnarray*} F_{n+1} & = & F_n + F_{n-1} \\ & \stackrel{I.V.}{=} & \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right) + \frac{1}{\sqrt{5}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} - \left( \frac{1-\sqrt{5}}{2} \right)^{n-1} \right) \\ & = & \frac{1}{\sqrt{5}} \left( \underbrace{ \left( \left( \frac{1+\sqrt{5}}{2} \right)^n + \left( \frac{1+\sqrt{5}}{2} \right)^{n-1} \right) }_{(*)} - \underbrace{ \left( \left( \frac{1-\sqrt{5}}{2} \right)^n + \left( \frac{1-\sqrt{5}}{2} \right)^{n-1} \right) }_{(**)} \right) \end{eqnarray*} Wir betrachten die beiden Klammerterme $(*)$ und $(**)$. \begin{eqnarray*} (*) & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \left(\frac{1+\sqrt{5}}{2} + 1\right) \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \cdot \frac{3+\sqrt{5}}{2} \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \cdot \frac{6+2\sqrt{5}}{4} \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \cdot \frac{1+2\sqrt{5}+5}{4} \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} \left(\frac{1+\sqrt{5}}{2}\right)^2 \\ & = & \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} \end{eqnarray*} Auf analoge Weise erhalten wir \[ (**) = \left(\frac{1-\sqrt{5}}{2}\right)^{n+1}. \] Setzen wir die kompakten Formeln für $(*)$ und $(**)$ oben ein, ergibt sich \[ F_{n+1} = \frac{1}{\sqrt{5}} \left( \left(\frac{1+\sqrt{5}}{2}\right)^{n+1} - \left(\frac{1-\sqrt{5}}{2}\right)^{n+1} \right). \] Damit ist die Formel von Moivre-Binet bewiesen.
Der Beweis in Übung 1 ist ein Beispiel dafür, wie wir nachweisen können, dass eine explizite Formel eine rekursiv definierte Folge korrekt beschreibt. Dies ist typischerweise mithilfe der Technik der vollständigen Induktion leicht möglich.
Deutlich schwieriger ist es aber, allein aus der rekursiven Definition einer Folge solch eine explizite Formel herzuleiten. Nichtdestotrotz werden wir in späteren Blogs sehen, dass uns die Analysis Methoden zur Vergügung stellt, mit denen wir in bestimmten Fällen aus der rekursiven Definition einer Folge eine explizite Formel entwickeln können. Insbesondere werde ich dann zeigen, wie wir die Formel von Moivre-Binet aus der Definition der Fibonacci-Zahlen herleiten können.
Teilen und Drucken