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

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

,

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:

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

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.

bzw.

an+2 = 4an+1 + an + 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

.

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

= .

Mit der Standard-Lösungsmethode kommen wir über

auf das Gleichungssystem

mit der Lösung

,

woraus sich nach Umwandlung der Nenner die gesuchte Form ergibt

,

mit der Abschätzung

.