In diesem Beitrag erläutern wir eine universelle Formel, mit der sich lineare Rekursionsgleichungen auflösen lassen. Zuvor wenden wir aber eine recht handliche Lösungsmethode an:

Bemerkung:

Jede reelle oder komplexe Zahlenfolge lässt sich als Abbildung f von der Menge IN ∪ {0} in die komplexen Zahlen |C auffassen. Unser Ziel ist die Auflösung der linearen Rekursionsgleichung

f(n+j) = λo·f(n) + λ1·f(n+1) + ... + λj-1·f(n+j-1)

für alle λi ∈ |C mit λo ≠ 0. Die zugehörigen Lösungsfunktionen bilden einen |C-Vektorraum V der Dimension j, wobei jede spezielle Lösung anhand der Werte  f(0),  f(1), ... f(j-1)  eindeutig definiert ist. Die übliche Addition von Funktionen liefert die additive Verknüpfung auf V, ebenso anschaulich ist die skalare Multiplikation definiert. Um eine Basis von V zu konstruieren, betrachten wir das (charakteristische) Polynom g mit

g(x) = x^j - λj-1·x^j-1 - λj-2·x^j-2 - ... - λ1·x - λo.

(Wir verzichten hier auf eine Herleitung des Polynoms g, um den Rahmen dieses Beitrags nicht zu sprengen. Die Herleitung ist übrigens auch im Spezialfall der Fibonaccizahlen vollkommen anders, als es in den meisten populärwissenschaftlichen Beiträgen dargestellt wird.)

Aus dem Fundamentalsatz der Algebra folgt, dass g über dem Körper |C der komplexen Zahlen genau m ≤ j paarweise verschiedene Nullstellen b₁,..., b_m mit der Vielfachheit t₁,..., t_m und t₁ + ... + t_m = j besitzt. Unter Verwendung dieser Nullstellen definiert man die folgenden Funktionen g_ik, die eine |C-Basis von V bilden:

g_ik(n):= nⁱ·b_kⁿ   mit g_0k(0):= 1   (k = 1, ... , m ;   i = 0, .... , t_k-1).

Wenn man nun irgendeine spezielle Lösung f ∈ V als Linearkombination dieser Funktionen schreibt, so ergibt das die explizite Darstellung von f.

Beispiel:   Alle Fibonaccifolgen (mit 2 beliebigen Startwerten f(0) und f(1) ) genügen der linearen Rekursionsgleichung f(n+2) = 1·f(n) + 1·f(n+1). Das charakteristische Polynom x² - x -1 hat die Nullstellen b_1,2 = ½·(1 ± √5 ). Daher bilden die Funktionen g₀₁, g₀₂ mit g₀₁(n) = b₁ⁿ und g₀₂(n) = b₂ⁿ eine |C-Basis des zweidimensionalen „Fibonacci-Raumes”:

V = { f:IN ∪ {0} → |C mit f(n+2) = 1·f(n) + 1·f(n+1)}.

Somit existieren für jedes f ∈ V eindeutig bestimmte komplexe Zahlen w, z mit w·g₀₁ + z ·g₀₂ = f. Die Fibonaccizahlen 0, 1, 1, 2, ... bilden eine solche Folge f ∈ V, die durch die beiden Startwerte f(0) = 0 und f(1) = 1 eindeutig bestimmt ist. Um die explizite Darstellung von f zu berechnen, ist also das folgende Gleichungssystem zu lösen:

w·g₀₁(0) + z·g₀₂(0) = f(0) = 0
w·g₀₁(1) + z·g₀₂(1) = f(1) = 1.

Aus den zwei Lösungen w = 1/√5  und z = -1/√5  erhält man die Gleichung f(n) = 1/√5 ·g₀₁(n) - 1/√5 ·g₀₂(n), die als „Formel von Binet” bekannt ist.