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

Aus Wikibooks

Wechseln zu: Navigation, Suche

Bei genauerer Betrachtung der Fibonacci-Folge

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

fällt auf, dass die Glieder der Teilfolge

f3n+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 an. Dazu ist es notwendig, auch an-1 und an-2 durch fn 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 fn ist es möglich, f3n+1 durch f3n-2 und f3n-5 auszudrücken:

fn = fn-1 + fn-2
\begin{align} 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{align}

Daraus folgt wiederum für an

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

und wir erhalten die Rekurrenz

an = 4an-1 + an-2 + 2,     a0=0, a1=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\ge0}a_nx^n \quad=\quad 4\frac{A(x)}{x} + \frac{A(x)-x}{x^2} + 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\sqrt5.

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{align} 0 &= -r_-C-r_+D+E\\ 1 &= (1+r_-)C+(1+r_+)D-4E\\ 1 &= -C-D-E \end{align}

mit der Lösung

C=\frac{3\sqrt5-5}{20},\quad D=\frac{-3\sqrt5-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((\sqrt5+5)(\sqrt5+2)^n+(-\sqrt5+5)(-\sqrt5+2)^n\big),

mit der Abschätzung

a_n\sim-\tfrac{1}{2}+\tfrac{1}{20}(\sqrt5+5)(\sqrt5+2)^n.
Von „http://de.wikibooks.org/wiki/Lineare_Rekurrenzen,_Potenzreihen_und_ihre_erzeugenden_Funktionen/_Eine_Fibonacci-Teilfolge“
Persönliche Werkzeuge