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

Aus Wikibooks

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)

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

haben jedoch die Anfangswerte a0=2, a1=1, und ergeben daher eine andere Zahlenfolge:

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

Erzeugende Funktion[Bearbeiten]

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 nm (m ganz) und solche der Form cn (c komplex) erlaubt sind.

Beispiele:

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) = = = 2 + x + 3x2 + 4x3 + 7x4 + ...

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

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:

Und hier die Potenzreihen wieder waagrecht:

= +

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

= L(x),
= ,
= ,

bekommt die Rekurrenz (1) die Form

= + L(x),

woraus mit den entsprechenden Startwerten anfolgt

.

Geschlossene Form[Bearbeiten]

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:

=

Nach Berechnung von A und B und weiterer Manipulation folgt

, mit .

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

anwenden und wir erhalten endlich für die Lucaszahlen an

und daher die Formel von Binet

.