Anwendung JNF: rekursive Folgen

Eine rekursive Folge n-ten Grades ist eine Gleichung der Form:

Wenn die Anfangsglieder

gegeben sind, sind damit alle Glieder eindeutig bestimmt. Die Frage ist nun ob eine explizite Formel für

existiert, und wenn ja, wie sie dann aussieht. Wenn man solch eine explizite Formel hätte wäre es nämlich ein leichtes z.B.

auszurechnen ohne vorher alle vorhergehenden Glieder der Folge bestimmen zu müssen.
Nun mit Hilfe der JNF erhält man eine Möglichkeit eine explizite Formel anzugeben. Man schreibt zunächst die Formel als Matrixprodukt:

wobei der Vektor auf der linken Seite mit

und, der auf der rechten Seite mit

bezeichnet sei. Die Matrix dazwischen heiße

Es gilt:

Da das Potenzieren von Matrizen in JNF ein leichtes ist, bestimme man deshalb die JNF von A, sie sei J.

Dann gilt:

Somit ist eine explizite Formel für

und damit auch für

gegeben.

Und hier das rettende Beispiel.

Jan Wendler
Erstellt am 10-01-95, zuletzt geändert 11-01-95