Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Ein Hauptsatz

Für das Verständnis linearer Rekurrenzen ist es zentral, den folgenden Hauptsatz und seine Folgerungen zu kennen.

Satz. Jede homogene lineare Rekurrenz erzeugt eine Zahlenfolge, die als Koeffizienten in einer Potenzreihe von einer rationalen Funktion erzeugt wird, wobei der Nenner der erzeugenden Funktion ein Polynom ist, dessen Koeffizienten mit den Koeffizienten der entsprechenden Rekurrenz identisch sind, wenn die Gleichung gleich Null gesetzt wird.

Damit besteht eine bijektive Zuordnung zwischen rationalen Funktionen und homogenen linearen Rekurrenzen. Als Beispiel siehe das vorhergehende Kapitel über die Lucaszahlen. Setzen wir die Differenzengleichung der Lucaszahlen auf Null, lautet sie:

$\,a_{n+2}-a_{n+1}-a_{n}=0$

mit den Koeffizienten 1, -1, -1 gleich denen des Nennerpolynoms von L(x).

Der Beweis ist einfach, man verfahre so wie im Beispiel bei der Herleitung der erzeugenden Funktion. Die nachstehenden Folgesätze ergeben sich unmittelbar:

Satz. Der Grad des Nennerpolynoms der erzeugenden Funktion ist gleich der Ordnung der entsprechenden linearen Rekurrenz.

Die wichtigste Schlußfolgerung ergibt sich jedoch durch Anwendung des Fundamentalsatzes der Algebra und der zuvor gefundenen Potenzreihen-Identitäten.

Satz. Jede lineare Rekurrenz hat eine geschlossene Form der Art

$\,a_{n}=\sum _{j=1}^{D}{\frac {1}{z_{j}^{n}}}\sum _{k=1}^{M_{j}}c_{j,k}n^{k-1}$,

wobei D die Ordnung der Rekurrenz, z_j eine (auch komplexe) Nullstelle des Nennerpolynoms der erzeugenden Funktion, M_j die Vielfachheit dieser Nullstelle, und die c_j,k rationale Konstanten sind, die es schlußendlich herauszufinden gilt.

Siehe den Buchteil Ausführliche Beispiele, wo das Finden der geschlossenen Form ein zentrales Thema ist.

Satz. Das asymptotische Verhalten einer linearen Rekurrenz ist exponentiell. Die Basis der Potenz ist das betragsmäßig größte Inverse aller Nullstellen des Nennerpolynoms der erzeugenden Funktion.

Auch dies ergibt sich unmittelbar, und damit kann das asymptotische Verhalten einer linearen Rekurrenz direkt aus der Differenzengleichung berechnet werden, wenn sie in der homogenen Form ist.

Als Beispiel die Formel 2ⁿ+3ⁿ mit der Rekurrenz

$a_{n+2}=5a_{n+1}-6a_{n},\qquad a_{0}=2,a_{1}=5$,

der das Nennerpolynom 1-5x+6x² mit den Nullstellen 1/2 und 1/3 entspricht. Zu beachten ist, dass Nullstellen auch komplex sein können.