Der italienische Mathematiker Leonardo von Pisa (Fibonacci genannt) beobachtete im Garten die Kaninchen und fragte sich:

Ein Paar neugeborener Kaninchen wirft nach zwei Monaten ein neues Paar und in den folgenden Monaten jeweils ein weiteres Paar. Jedes Paar vermehrt sich genauso. Wie viele Paare gibt es (Todesfälle ausgeschlossen) im Jahresverlauf ?

Von Monat zu Monat ist 1, 1, 2, 3, 5, 8, ... die Anzahl der Kaninchenpaare - jede Zahl > 1 ist die Summe der beiden vorangegangenen Zahlen. Dieses Verfahren lässt sich auf verschiedene Phänomene anwenden, wobei meist viel größere Zahlen gesucht sind. Anstatt ständig zu addieren, kann man dann die Formel von Jaques Binet (1786 - 1856) anwenden:

Bemerkung:

Die Formel von Binet liefert zum Beispiel für n = 30 die Fibonaccizahl:

 =  832040.

Wir haben oben die Herleitung von Binets Formel skizziert und wollen das jetzt ausführlich darlegen: Die Gleichung an+1 = an + an-1 erweitern wir zum linearen Gleichungssystem

Die obige Matrix bezeichnen wir mit A und erhalten sukzessive:

Um die Matrix Aⁿ effektiv berechnen zu können, fassen wir A als lineare Abbildung (Endomorphismus) h auf, die den Vektor (v₁,v₂)^t ∈ IR² auf den Vektor (v₁+v₂, v₁)^t  abbildet. Wir suchen jetzt eine IR²-Basis (u,v), so dass h in Bezug auf diese Basis einer Diagonalmatrix

entspricht, deren Potenzen man explizit bestimmen kann. Die Zahlen λ und μ bezeichnet man als Eigenwerte von h, sie sind die beiden Nullstellen des charakteristischen Polynoms  x² - x - 1 von h. Daraus folgt: λ = ½ + ½·√5 und μ = ½ - ½·√5.   Das Additionsverfahren liefert mit Hilfe der Eigenwerte die gesuchten Basisvektoren

die man als Eigenvektoren von h bezeichnet. Bezüglich (u,v) korrespondiert der Endomorphismus h daher zur Diagonalmatrix

Die Vektoren u, v fassen wir zu einer Matrix B zusammen und bezeichnen die zu B inverse Matrix mit B^-1. Es gilt: A = B·D·B^-1 und daraus folgt: A² = (B·D·B^-1)·(B·D·B^-1) = (B·D) ·(B^-1·B) · (D·B^-1) = B·D²·B^-1. Daraus folgt schließlich: Aⁿ  =  B·Dⁿ·B^-1. Damit erhalten wir:

Nun kann man das Produkt Aⁿ·(1,0)^t  berechnen und erhält Binets Formel.

Dieses Verfahren lässt sich auf alle linearen Rekursionsgleichungen vom Typ an+1 = r·an + s·an-1 übertragen, falls A (also der korrespondierende Endomorphismus h) zwei verschiedene reelle Eigenwerte besitzt. Sonst kann man wie folgt vorgehen:

1. Fall  (Jordansche Normalform)  -  die jeweilige 2×2-Matrix A hat genau einen (doppelten reellen) Eigenwert λ: Wir bezeichnen die Einheitsmatrix mit E, dann besteht die Matrix A - λ·E aus den Zeilen r-λ  s, 1  -λ und ist somit nicht die Nullmatrix. Die Dimension des einzigen Eigenraumes Eλ ist also kleiner als 2, womit A nicht diagonalisierbar ist. Das charakteristische Polynom von A zerfällt aber in reelle Linearfaktoren, folglich existiert eine Basis (u, v) des IR², so dass A in Bezug auf die kanonische Basis sowie die obere Dreiecksmatrix

bezüglich der Basis (u,v) den gleichen Endomorphismus darstellen. Die Matrix B^-1 bewirke den entsprechenden Basiswechsel, dann folgt analog zum Fibonacci-Fall: Aⁿ = B·Jⁿ·B^-1. Die allgemeine n-te Potenz von J kann man explizit angeben, ferner lassen sich die Basisvektoren u, v und somit die Matrizen B, B^-1 problemlos berechnen. Zum Beispiel erhalten wir für die Rekursionsgleichung   an+1 = 2an - an-1  die Matrix Aⁿ =

Für beliebige Startwerte a₀, a₁ gilt daher: an = n·a₁ + (1-n)·a₀.

2. Fall - es existiert kein reeller Eigenwert:
Die 2×2-Matrix A hat daher zwei konjugiert-komplexe Eigenwerte λ, μ und ist folglich über dem Körper |C der komplexen Zahlen diagonalisierbar. Alle Berechnungen erfolgen analog zur reellen Diagonalisierung. Dabei sind die Rechenregeln für komplexe Zahlen zu beachten.

Ein Beispiel hierzu ist die Gleichung  an+1 = an - an-1.  Daraus folgt:   Aⁿ =

Für beliebige Startwerte a₀, a₁ erhalten wir damit das n-te Folgeglied an =

Diesem Term sieht man zunächst nicht an, dass er für reelle Startwerte selbstverständlich nur reelle Folgeglieder liefern kann, die sich außerdem periodisch wiederholen. Es entpuppt sich jedoch mit Hilfe der Relationen

die reelle Formel:

Die Zahlenfolge  an+1 = an - an-1   kann man allerdings auch einfacher in den Griff bekommen. Ansonsten ist das aber selten der Fall, wie sich etwa an der Fibonaccifolge zeigt, für die unser oben beschriebenes Verfahren die elementarste Methode ist, um die explizite Darstellung herzuleiten.