Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Ein Beispiel: Lucaszahlen

Dieses Kapitel ist ganz ähnlich gehalten wie ein entsprechendes Kapitel von Wilf in Generatingfunctionology über die Fibonaccizahlen.

Betrachten wir die Folge der Lucaszahlen. Diese sind, definiert durch die lineare Rekurrenz (für die Definition dieses Begriffs siehe dieses Kapitel)

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

haben jedoch (anders als die Fibonaccizahlen) die Anfangswerte a₀=2, a₁=1, und ergeben daher eine andere Zahlenfolge:

a_n = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...}.

Erzeugende Funktion

Als geschlossene Form wollen wir eine Funktion von n bezeichnen, die nur die arithmetischen Operationen Addition, Multiplikation und Potenzierung enthält, wobei nur Potenzen der Form n^m (m ganz) und solche der Form cⁿ (c komplex) erlaubt sind.

Beispiele: $f(n)=(5n^{3}+2n+1)\cdot 2^{n}+1,\quad f(n)=n^{2}+2n+1-(-1)^{n},\quad f(n)={\frac {i^{n}+(-i)^{n}}{2}}$

Wir wollen nun eine geschlossene Form für die Lucaszahlen finden.

Dazu setzen wir die Zahlen der Lucasfolge als Koeffizienten in eine formale Potenzreihe (mit formal ist gemeint, dass die Frage der Konvergenz dieser Reihe für uns irrelevant ist). Wir nehmen an, dass der Potenzreihe eine wie auch immer geartete erzeugende Funktion von x entspricht, und nennen sie L(x):

L(x) = $\,\sum _{n=0}^{\infty }a_{n}x^{n}$ = $a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots$ = 2 + x + 3x² + 4x³ + 7x⁴ + ...

Um die geschlossene Form zu finden, benötigen wir erst die erzeugende Funktion L(x). Dazu multiplizieren wir die Rekurrenz (1) mit xⁿ und summieren ins Unendliche:

$\,\sum _{n=0}^{\infty }a_{n+2}x^{n}=\sum _{n=0}^{\infty }a_{n+1}x^{n}+\sum _{n=0}^{\infty }a_{n}x^{n}$

Halt! höre ich die Leser rufen, was ist das? Hierbei handelt es sich um eine ungewöhnliche Manipulation, die aber völlig korrekt ist. Wenn wir die Potenzreihen senkrecht schreiben, sehen wir für jedes einzelne Element der Lucaszahlen seine eigene Rekurrenz:

${\begin{array}{rcccl}a_{2}&=&a_{1}&+&a_{0}\\+&&+&&+\\a_{3}x&=&a_{2}x&+&a_{1}x\\+&&+&&+\\a_{4}x^{2}&=&a_{3}x^{2}&+&a_{2}x^{2}\\+&&+&&+\\a_{5}x^{3}&=&a_{4}x^{3}&+&a_{3}x^{3}\\+&&+&&+\\\vdots &&\vdots &&\vdots \end{array}}$

Und hier die Potenzreihen wieder waagrecht:

$a_{2}+a_{3}x+a_{4}x^{2}+a_{5}x^{3}+\cdots$ = $a_{1}+a_{2}x+a_{3}x^{2}+a_{4}x^{3}+\cdots$ + $a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots$

Da aber diese Teilfolgen so durch L(x) beschrieben werden können:

$a_{0}+a_{1}x+a_{2}x^{2}+a_{3}x^{3}+\cdots$ = L(x),

$a_{1}+a_{2}x+a_{3}x^{2}+a_{4}x^{3}+\cdots$ = ${\frac {L(x)-a_{0}}{x}}$,

$a_{2}+a_{3}x+a_{4}x^{2}+a_{5}x^{3}+\cdots$ = ${\frac {{\frac {L(x)-a_{0}}{x}}-a_{1}}{x}}$,

bekommt die Rekurrenz (1) die Form

${\frac {{\frac {L(x)-a_{0}}{x}}-a_{1}}{x}}$ = ${\frac {L(x)-a_{0}}{x}}$ + L(x),

woraus mit den entsprechenden Startwerten a_n folgt

$L(x)={\frac {2-x}{1-x-x^{2}}}$.

Geschlossene Form

Da sich die erzeugende Funktion L(x) in zwei Partialbrüche mit einfacherem Nenner zerlegen lässt, ist davon auszugehen, dass sich auch die Lucaszahlen als Summe zweier Ausdrücke darstellen lassen. Durch Lösen der quadratischen Gleichung erhalten wir die Nullstellen des Polynoms im Nenner von L(x), und damit dessen Partialbruchzerlegung:

$L(x)={\frac {2-x}{1-x-x^{2}}}$ = ${\frac {2-x}{(x-q_{1})(x-q_{2})}}={\frac {A}{x-q_{1}}}+{\frac {B}{x-q_{2}}},\qquad q_{1}={\frac {1+{\sqrt {5}}}{2}},\quad q_{2}={\frac {1-{\sqrt {5}}}{2}}$

Nach Berechnung von A und B und weiterer Manipulation folgt

$L(x)={\frac {1}{1-r_{1}x}}+{\frac {1}{1-r_{2}x}}$, mit $r=1/q$.

In diese Form gebracht, lässt sich die Potenzreihen-Identität

${\frac {1}{1-cx}}=\sum _{n\geq 0}c^{n}x^{n}$

anwenden und wir erhalten endlich für die Lucaszahlen a_n

$\sum _{n\geq 0}a_{n}x^{n}=\sum _{n\geq 0}(r_{1})^{n}x^{n}+\sum _{n\geq 0}(r_{2})^{n}x^{n}$

und daher die Formel von Binet

$a_{n}=r_{1}^{n}+r_{2}^{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}$.