Explizite Formel für rekursive Beziehung

25.01.2022, 15:10	Der_Apfel	Auf diesen Beitrag antworten »
Explizite Formel für rekursive Beziehung Hallo, ich frage mich gerade, wie die explizite Formel für diese rekursive Beziehung $\begin{eqnarray} f_{I + 1} = f_{I} + f_{I - 1} + I \end{eqnarray}$ mit $\begin{eqnarray} f_0 = 0, f_1 = 1 \end{eqnarray}$ Es erinnert sehr an die Fibonacci-Folge, bis auf den addierten Index. Gibt es da einen Trick wie man mit Hilfe der expliziten Formel für die Fibonacci-Folge auf die Lösung kommt?
25.01.2022, 15:34	HAL 9000	Auf diesen Beitrag antworten »
inhomogene lineare Differenzengleichung Idee: Mit dem Ansatz $\begin{eqnarray} f_n = g_n + an+b \end{eqnarray}$ ("lineare Verschiebung") wollen wir erreichen, passende Konstanten $\begin{eqnarray} a,b \end{eqnarray}$ so zu finden, dass $\begin{eqnarray} (g_n) \end{eqnarray}$ eine Folge vom Fibonacci-Typ ist, d.h., $\begin{eqnarray} g_{I+1} = g_I + g_{I-1} \end{eqnarray}$ . Setzen wir also ein: $\begin{eqnarray} g_{I+1} + a(I+1)+b = g_I + aI + b + g_{I-1} + a(I-1) + b + I \end{eqnarray}$ . Jetzt die gewünschte Fibonacci-Eigenschaft von $\begin{eqnarray} (g_n) \end{eqnarray}$ einsetzen und nach ein paar Vereinfachungen Koeffizientenvergleich: $\begin{eqnarray} a(I+1)+b = aI + b + a(I-1) + b + I \end{eqnarray}$ $\begin{eqnarray} 0 = (a+1)I-2a + b \end{eqnarray}$ Das ergibt $\begin{eqnarray} a=-1 \end{eqnarray}$ sowie $\begin{eqnarray} b=-2 \end{eqnarray}$ , also $\begin{eqnarray} f_n = g_n - n - 2 \end{eqnarray}$ bzw. rückwärts $\begin{eqnarray} g_n = f_n + n + 2 \end{eqnarray}$ . Nun lässt sich jede Folge vom Fibonacci-Typ in der Weise $\begin{eqnarray} g_n = (g_1-g_0) F_n + g_0 F_{n+1} \end{eqnarray}$ darstellen, wobei $\begin{eqnarray} (F_n) \end{eqnarray}$ die Original-Fibonacci-Folge ist (d.h. mit $\begin{eqnarray} F_0=0,F_1=1,F_2=1,\ldots \end{eqnarray}$ ) Das bedeutet letztlich, dass $\begin{eqnarray} f_n = (f_1-f_0+1) F_n + (f_0+2) F_{n+1} - n - 2 \end{eqnarray}$ gilt. Mit deinen Anfangsbedingungen $\begin{eqnarray} f_0=0,f_1=1 \end{eqnarray}$ ergibt das $\begin{eqnarray} f_n = 2F_n + 2F_{n+1} - n - 2 = 2F_{n+2}-n-2 \end{eqnarray}$ EDIT (26.1.): Da hat wohl einer das Interesse verloren.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »