0 Daumen
2,3k Aufrufe

Hallo, liebe Mathematiker,

wir sollen eine geschlossene Formel für die Fibonacci-Zahlen herleiten. Auf Wikipedia steht die geschlossene Formel und ein kurzer Hinweis, wie die Herleitung funktioniert. Leider bin ich zu dumm oder zu unerfahren, um das zu verstehen. Kann mir hier vielleicht jemand erklären, wie man eine geschlossene Formel für die Fibonacci-Zahlen herleiten kann?

Avatar von

2 Antworten

+1 Daumen
 
Beste Antwort

Aloha :)

Die Fibonacci-Folge ist definiert als:$$f_1=1\;\;;\;\;f_2=1\;\;;\;\;f_n=f_{n-1}+f_{n-2}\;\;\text{für}\;\; n\ge3$$

Mit dem Ansatz \(f_n=\lambda\cdot f_{n-1}\) bzw. \(f_n=\lambda^n\) gehen wir in die Definitionsgleichung:$$\left.\lambda^n=\lambda^{n-1}+\lambda^{n-2}\quad\right|\;:\lambda^{n-2}$$$$\left.\lambda^2=\lambda+1\quad\right|\;-\lambda-1$$$$\left.\lambda^2-\lambda-1=0\quad\right|\;\text{pq-Formel}$$$$\lambda_{1;2}=\frac{1}{2}\pm\sqrt{\frac{1}{4}+1}=\frac{1}{2}\pm\frac{1}{2}\sqrt5=\frac{1\pm\sqrt5}{2}$$

Jede Linearkombination der gefundenen Lösungen ist wieder eine Lösung der Definitionsgleichung:$$f_n=a\left(\frac{1+\sqrt5}{2}\right)^n+b\left(\frac{1-\sqrt5}{2}\right)^n$$

Die beiden Unbekannten \(a\) und \(b\) erhalten wir aus den Anfangsbedingungen \(f_1=1\) und \(f_2=1\).$$1=f_1=a\left(\frac{1+\sqrt5}{2}\right)^1+b\left(\frac{1-\sqrt5}{2}\right)^1$$$$1=f_2=a\left(\frac{1+\sqrt5}{2}\right)^2+b\left(\frac{1-\sqrt5}{2}\right)^2$$

Die Lösung dieses Gleichungssystems ist \(a=1/\sqrt5\) und \(b=-1/\sqrt5\). Das liefert uns schließlich die gesuchte geschlossene Darstellung:$$f_n=\frac{1}{\sqrt5}\left(\frac{1+\sqrt5}{2}\right)^n-\frac{1}{\sqrt5}\left(\frac{1-\sqrt5}{2}\right)^n$$

Avatar von 148 k 🚀

Vielen Dank für diese sehr verständliche Herleitung. So kann man Mathematik verstehen!!!

Wie kommst Du auf den Ansatz \(f_n=\lambda\cdot f_{n-1}\) bzw. \(f_n=\lambda^n\)?

Bilde mal grundsätzlich den Quotienten f(n + 1)/f(n)

Du wirst feststellen das je größer n wird desto mehr stabilisiert sich das Ergebnis um einen festen Wert. Daher der Ansatz.

blob.png

Jede Linearkombination der gefundenen Lösungen ist wieder eine Lösung der Definitionsgleichung

Die umgekehrte Frage :  "Warum ist jede Darstellung der Fibonacci-Folge eine Linearkombination dieser zwei ?"  sollte aber auch beantwortet werden.

+1 Daumen

Verwende alternativ den Ansatz

$$ \begin{pmatrix} f_{n}\\f_{n-1}\end{pmatrix} = \begin{pmatrix} 1&1\\1&0\end{pmatrix}\begin{pmatrix} f_{n-1}\\f_{n-2} \end{pmatrix}, \quad n\ge 3$$

$$ \begin{pmatrix} f_{2}\\f_1 \end{pmatrix} =\begin{pmatrix} 1\\1 \end{pmatrix}$$

Wandle diese rekursive Gleichung durch Diagonalisierung in eine explizite um.

Avatar von 6,0 k

Ich finde dieses Ansatz viel schöner. Ich selber habe es damals auch so hergeleitet.

Daher habe ich mal den Kommentar in eine eigene Antwort gewandelt.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community