Fibonacci-Folge

27.11.2018, 15:10

yannik0103

Fibonacci-Folge

Meine Frage:
Hallo, ich habe folgende Aufgabe:
Gegeben ist die Dreitermrekursion $\begin{eqnarray*} F_{n+1} = F_{n} + F_{n-1} \end{eqnarray*}$ mit Startwerten $\begin{eqnarray*} F_{0} = 0 \end{eqnarray*}$ und $\begin{eqnarray*} F_{1} = 1 \end{eqnarray*}$ . Bestimmen Sie $\begin{eqnarray*} \lim_{n \to \infty } \frac{F_{n} }{F_{n+1} } \end{eqnarray*}$ und $\begin{eqnarray*} \lim_{n \to \infty } \frac{F_{n-1} }{F_{n+1} } \end{eqnarray*}$

Meine Ideen:
Ich habe leider keinen richtigen Ansatz, da ich nicht sehe wie ich die Brüche vereinfachen soll. Mein erster Ansatz war der goldene Schnitt, doch der ist der Grenzwert des Kehrwerts.

27.11.2018, 16:37

HAL 9000

Auf diesen Beitrag antworten »

Das íst die Fibonacci-Folge, für die kann man die Formel_von_Moivre/Binet nachweisen und damit dann den gesuchten Grenzwert bestimmen.

27.11.2018, 17:11

yannik0103

Auf diesen Beitrag antworten »

Ok ich habe die Formel zu $\begin{eqnarray*} \frac{1}{2} \lim_{n \to \infty } \frac{(1+ \sqrt{5}) ^{n}- (1-\sqrt{5})^{n} }{(1+\sqrt{5}) ^{n-1}- (1-\sqrt{5} )^{n-1} } \end{eqnarray*}$ vereinfacht, aber wie kann ich jetzt den Grenzwert bestimmen?

27.11.2018, 17:45

yannik0103

Auf diesen Beitrag antworten »

Unten muss im Exponenten n+1 stehen, habe mich vertippt. Und vor dem limes muss dementsprechend auch 2 stehen

27.11.2018, 19:13

HAL 9000

Auf diesen Beitrag antworten »

Ja was wohl: In Zähler und Nenner den dominanten Faktor ausklammern und dann kürzen, das ist doch Standardvorgehen!

$\begin{eqnarray*} \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{(1+\sqrt{5})^{n-1}-(1-\sqrt{5})^{n-1}} = \frac{(1+\sqrt{5})^n}{(1+\sqrt{5})^{n-1}}\cdot \frac{1-(1+\sqrt{5})^{-n}(1-\sqrt{5})^n}{1-(1+\sqrt{5})^{-(n-1)}(1-\sqrt{5})^{n-1}} = (1+\sqrt{5})\cdot \frac{1-q^n}{1-q^{n-1}} \end{eqnarray*}$

basierend auf $\begin{eqnarray*} q= (1+\sqrt{5})^{-1}(1-\sqrt{5}) = -\frac{(1-\sqrt{5})^2}{4} = -\frac{3-\sqrt{5}}{2} \end{eqnarray*}$ , für die gilt $\begin{eqnarray*} |q|<1 \end{eqnarray*}$ .

Zähler und Nenner im übrig bleibenden Bruch rechts konvergieren jeweils gegen 1, also auch der Quotient.

28.11.2018, 07:34

Leopold

Auf diesen Beitrag antworten »

Die Existenz der Grenzwerte $\begin{align*} \alpha \end{align*}$ und $\begin{align*} \beta \end{align*}$ für die beiden Bruchfolgen vorausgesetzt, kann man sie auch direkt aus der Rekursionformel erhalten. Man dividiert durch das mittlere Glied: $\begin{align*} \frac{F_{n+1}}{F_n} = 1 + \frac{F_{n-1}}{F_n} \end{align*}$ , und erhält für $\begin{align*} n \to \infty \end{align*}$ daraus

$\begin{align*} \frac{1}{\alpha} = 1 + \alpha \end{align*}$

Da die Folgenglieder positiv sind, ist die positive Lösung der hieraus abgeleiteten quadratischen Gleichung der gesuchte Grenzwert $\begin{align*} \alpha \end{align*}$ .

Ähnlich findet man dann auch

$\begin{align*} \alpha + \beta = 1 \end{align*}$

28.11.2018, 07:58

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Leopold
Die Existenz der Grenzwerte $\begin{align*} \alpha \end{align*}$ und $\begin{align*} \beta \end{align*}$ für die beiden Bruchfolgen vorausgesetzt

Ein gewaltiger Haken an der Sache, und der Grund dafür, warum ich diesen Vorschlag nicht gemacht habe. Augenzwinkern

28.11.2018, 08:13

Leopold

Auf diesen Beitrag antworten »

$\begin{align*} \varepsilon_n = \left| \frac{F_n}{F_{n+1}} - \alpha \right| \end{align*}$

Man bekommt damit

$\begin{align*} \varepsilon_n = \frac{1}{F_{n+1}} \left| F_n - \alpha F_{n+1} \right| = \frac{1}{F_{n+1}} \left| F_n - \alpha \left( F_n + F_{n-1} \right) \right| = \frac{1}{F_{n+1}} \left| (1 - \alpha) F_n - \alpha F_{n-1} \right| \end{align*}$

$\begin{align*} = \frac{1}{F_{n+1}} \left| \alpha^2 F_n - \alpha F_{n-1} \right| = \frac{\alpha}{F_{n+1}} \left| F_{n-1} - \alpha F_n \right| \end{align*}$

Und iterativ endet das bei

$\begin{align*} \varepsilon_n = \frac{\alpha^n}{F_{n+1}} \left| F_0 - \alpha F_1 \right| = \frac{\alpha^{n+1}}{F_{n+1}} \end{align*}$

EDIT

Es gibt viele höchst elegante Verfahren, die Formel von Binet herzuleiten. Die meisten sind aber dem Anfänger nicht unmittelbar zugänglich. Wenn man die Rechnung oben noch etwas verfeinert, kann man "zu Fuß" zu dieser Formel kommen.

Rechnet man ohne Beträge, erhält man

$\begin{align*} \frac{F_n}{F_{n+1}} - \alpha = \frac{(-1)^{n+1} \alpha^{n+1}}{F_{n+1}} \end{align*}$

Man löst das nach dem Glied mit der höheren Nummer auf und erhält nach Umnummerierung

$\begin{align*} F_n = \frac{1}{\alpha} F_{n-1} + (-1)^{n-1} \alpha^{n-1} \end{align*}$

Damit ist die Rekursionstiefe schon einmal um einen Schritt verringert. Und jetzt muß man das eigentlich nur immer wieder iterativ auf die nächstkleinere Nummer anwenden:

$\begin{align*} F_n = \frac{1}{\alpha} F_{n-1} + (-1)^{n-1} \alpha^{n-1} \end{align*}$

$\begin{align*} = \frac{1}{\alpha} \left( \frac{1}{\alpha} F_{n-2} + (-1)^{n-2} \alpha^{n-2} \right) + (-1)^{n-1} \alpha^{n-1} \end{align*}$

$\begin{align*} = \frac{1}{\alpha^2} F_{n-2} + (-1)^{n-2} \alpha^{n-3} + (-1)^{n-1} \alpha^{n-1} \end{align*}$

$\begin{align*} = \frac{1}{\alpha^2} \left( \frac{1}{\alpha} F_{n-3} + (-1)^{n-3} \alpha^{n-3} \right) + (-1)^{n-2} \alpha^{n-3} + (-1)^{n-1} \alpha^{n-1} \end{align*}$

$\begin{align*} = \frac{1}{\alpha^3} F_{n-3} + (-1)^{n-3} \alpha^{n-5} + (-1)^{n-2} \alpha^{n-3} + (-1)^{n-1} \alpha^{n-1} \end{align*}$

Das Ganze endet schließlich bei

$\begin{align*} = \frac{1}{\alpha^{n-1}} F_1 + (-1)^1 \alpha^{-n+3} + (-1)^2 \alpha^{-n+5} + \ldots + (-1)^{n-1} \alpha^{n-1} \end{align*}$

$\begin{align*} = (-1)^0 \alpha^{-n+1} + (-1)^1 \alpha^{-n+3} + (-1)^2 \alpha^{-n+5} + \ldots + (-1)^{n-1} \alpha^{n-1} \end{align*}$

Damit gilt

$\begin{align*} F_n = \alpha^{-n+1} \left( 1 - \alpha^2 + \alpha^4 \mp \ldots + (-1)^{n-1} \alpha^{2n-2} \right) = \alpha^{-n+1} \cdot \frac{1 + (-1)^{n+1} \alpha^{2n}}{1 + \alpha^2} \end{align*}$

$\begin{align*} = \frac{\alpha}{1 + \alpha^2} \cdot \left( \alpha^{-n} + (-1)^{n+1} \alpha^n \right) = \frac{\sqrt{5}}{5} \left( \alpha^{-n} + (-1)^{n+1} \alpha^n \right) \end{align*}$

Außer Konzentration, richtig zählen und der Formel für eine geometrische Summe braucht man nichts Weiteres für diesen Weg. Und wenn ich mich beim Rückwärtsrechnen nicht irgendwo verzählt habe, dann stimmt das sogar.

03.12.2018, 08:34

HAL 9000

Auf diesen Beitrag antworten »

Wenn es so ausartet, dann kann man auch gleich folgendes sagen:

Betrachten wir allgemein eine Differenzengleichung zweiten Grades $\begin{eqnarray*} x_n = ux_{n-1}+vx_{n-2} \end{eqnarray*}$ mit der Eigenschaft, dass für die beiden Lösungen der charakteristischen Gleichung $\begin{eqnarray*} \lambda^2-u\lambda-v=0 \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} |\lambda_1|>|\lambda_2| \end{eqnarray*}$ gelten möge. Dann haben alle Lösungen dieser Gleichung die Gestalt $\begin{eqnarray*} x_n =C_1\lambda_1^n + C_2\lambda_2^n \end{eqnarray*}$ mit Konstanten $\begin{eqnarray*} C_1,C_2 \end{eqnarray*}$ , die sich aus den Anfangsbedingungen ergeben. Kann man zudem $\begin{eqnarray*} C_1\neq 0 \end{eqnarray*}$ nachweisen, so folgt unmittelbar $\begin{eqnarray*} \lim_{n\to\infty} \frac{x_{n+1}}{x_n}=\lambda_1 \end{eqnarray*}$ .

Im vorliegenden Fall $\begin{eqnarray*} u=1,v=1 \end{eqnarray*}$ ist $\begin{eqnarray*} \lambda_1 = \frac{1+\sqrt{5}}{2} \end{eqnarray*}$ und $\begin{eqnarray*} \lambda_2=\frac{1-\sqrt{5}}{2} \end{eqnarray*}$ . Aus $\begin{eqnarray*} C_1=0 \end{eqnarray*}$ würde $\begin{eqnarray*} \lim_{n\to\infty} F_n=0 \end{eqnarray*}$ folgen, was für die Fibonaccifolge sicher nicht stimmt, daher ist hier $\begin{eqnarray*} C_1\neq 0 \end{eqnarray*}$ und somit $\begin{eqnarray*} \lim_{n\to\infty} \frac{F_{n+1}}{F_n}=\lambda_1=\frac{1+\sqrt{5}}{2} \end{eqnarray*}$ .

Neue Frage »

Antworten »

Fibonacci-Folge

Verwandte Themen