Zum Inhalt springen

Lineare Rekurrenzen, Potenzreihen und ihre erzeugenden Funktionen/ Ein Hauptsatz

Aus Wikibooks

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:

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
,
wobei D die Ordnung der Rekurrenz, zj eine (auch komplexe) Nullstelle des Nennerpolynoms der erzeugenden Funktion, Mj die Vielfachheit dieser Nullstelle, und die cj,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 2n+3n mit der Rekurrenz

,

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