Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Eine Fibonacci-Teilfolge

Bei genauerer Betrachtung der Fibonacci-Folge

f_n = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...}

fällt auf, dass die Glieder der Teilfolge

f_3n+1 = {1, 3, 13, 55, 233, 987, 4181, ...}

alle ungerade zu sein scheinen, was wir zunächst ohne Beweis voraussetzen. Angenommen, uns interessiert die Folge, die sich durch Verringerung um 1 und anschließender Halbierung dieser Werte ergibt, also

$a_{n}={\frac {f_{3n+1}-1}{2}}=\{0,1,6,27,116,493,2090,8855,37512,158905,\ldots \}$,

und wir wollen eine geschlossene Form dafür finden, dann brauchen wir zuerst eine Rekurrenz für a_n. Dazu ist es notwendig, auch a_n-1 und a_n-2 durch f_n auszudrücken:

$a_{n}={\frac {f_{3n+1}-1}{2}}\quad \Longrightarrow \quad a_{n-1}={\frac {f_{3n-2}-1}{2}},\quad a_{n-2}={\frac {f_{3n-5}-1}{2}}.$

Durch einfache Manipulationen und Kenntnis der Rekurrenz für f_n ist es möglich, f_3n+1 durch f_3n-2 und f_3n-5 auszudrücken:

f_n = f_n-1 + f_n-2

${\begin{aligned}f_{3n+1}&=f_{3n}+f_{3n-1}\\&=2f_{3n-1}+f_{3n-2}\\&=3f_{3n-2}+2f_{3n-3}\\&=4f_{3n-2}+f_{3n-3}-f_{3n-4}\\&=4f_{3n-2}+f_{3n-5}\end{aligned}}$

Daraus folgt wiederum für a_n

2a_n+1 = 4(2a_n-1+1) + (2a_n-2+1),

und wir erhalten die Rekurrenz

a_n = 4a_n-1 + a_n-2 + 2,     a₀=0, a₁=1.

bzw.

a_n+2 = 4a_n+1 + a_n + 2,     a₀=0, a₁=1.

Die Inhomogenität der Rekurrenz spielt keine Rolle bei der Berechnung der erzeugenden Funktion A(x), solange sich zusätzliche Ausdrücke als Potenzreihe darstellen lassen, und wir erhalten

$A(x)=\sum _{n\geq 0}a_{n}x^{n}\quad =\quad {\frac {A(x)-x}{x^{2}}}-4{\frac {A(x)}{x}}-2{\frac {1}{1-x}}$

$A(x)={\frac {x+x^{2}}{(1-x)(1-4x-x^{2})}}$.

Lösung der quadratischen Nennerfaktor-Gleichung liefert den Ansatz für die Partialbruchzerlegung

$A(x)={\frac {x+x^{2}}{(1-x)(1-4x-x^{2})}}$ = ${\frac {C}{x-r_{+}}}+{\frac {D}{x-r_{-}}}+{\frac {E}{1-x}},\qquad r_{\pm }=-2\pm {\sqrt {5}}$.

Mit der Standard-Lösungsmethode kommen wir über

$\,x+x^{2}=C(x-r_{-})(1-x)+D(x-r_{+})(1-x)+E(1-4x-x^{2})$

$\,x+x^{2}=C((1+r_{-})x-r_{-}-x^{2})+D((1+r_{+})x-r_{+}-x^{2})+E(1-4x-x^{2})$

auf das Gleichungssystem

${\begin{aligned}0&=-r_{-}C-r_{+}D+E\\1&=(1+r_{-})C+(1+r_{+})D-4E\\1&=-C-D-E\end{aligned}}$

mit der Lösung

$C={\frac {3{\sqrt {5}}-5}{20}},\quad D={\frac {-3{\sqrt {5}}-5}{20}},\quad E=-{\frac {1}{2}}$,

woraus sich nach Umwandlung der Nenner die gesuchte Form ergibt

$a_{n}=-{\tfrac {1}{2}}+{\tfrac {1}{20}}{\big (}({\sqrt {5}}+5)({\sqrt {5}}+2)^{n}+(-{\sqrt {5}}+5)(-{\sqrt {5}}+2)^{n}{\big )}$,

mit der Abschätzung

$a_{n}\sim -{\tfrac {1}{2}}+{\tfrac {1}{20}}({\sqrt {5}}+5)({\sqrt {5}}+2)^{n}$.