Wie von Werner schon hingeschrieben gilt
$$ (1) \quad \begin{pmatrix} x_{n+1} \\ x_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_n \\ x_{n-1} \end{pmatrix} $$ und sei \( A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \)
\( A \) hat zwei verschieden Eigenwerte \( \alpha \) und \( \beta \) die Lösung der Gleichung \( \lambda^2 - \lambda - 1 = \) sind.
Wegen dem Satz von Vieta gilt für die beiden Lösungen
$$ (2) \quad \alpha + \beta = 1 $$ und
$$ (3) \quad \alpha \cdot \beta = -1 $$
Aus (1) folgt durch mehfache Anwendung die Gleichung
$$ (4) \quad \begin{pmatrix} x_{n+1} \\ x_n \end{pmatrix} = A^n \begin{pmatrix} x_1 \\ x_0 \end{pmatrix} $$
Die Matrix \( A \) kann diagonalisiert werden durch die Matrix
\( T = \begin{pmatrix} \alpha & 1 \\ \beta & 1 \end{pmatrix} \) und es gilt
\( T^{-1} A T = D = \begin{pmatrix} \alpha & 0 \\ 0 & \beta \end{pmatrix} \)
Damit gilt
$$ (5) \quad \begin{pmatrix} x_{n+1} \\ x_n \end{pmatrix} = T D^n T^{-1} \begin{pmatrix} x_1 \\ x_0 \end{pmatrix} $$
dabei gilt \( D^n = \begin{pmatrix} \alpha^n & 0 \\ 0 & \beta^n \end{pmatrix} \)
Mit den Anfangswerten \( x_1 = x_0 = 1 \) folgt aus (5)
$$ \begin{pmatrix} x_{n+1} \\ x_n \end{pmatrix} = \frac{1}{\beta-\alpha} \begin{pmatrix} \alpha^{n+1}(\beta-1) + \beta^{n+1}(1-\alpha) \\ \alpha^n(\beta-1) + \beta^n(1-\alpha) \end{pmatrix} $$
Wegen (2) folgt jetzt
$$ \begin{pmatrix} x_{n+1} \\ x_n \end{pmatrix} = \frac{1}{\sqrt{5}} \begin{pmatrix} \alpha^{n+2} - \beta^{n+2} \\ \alpha^{n+1} - \beta^{n+1} \end{pmatrix} $$ also
$$ x_n = \frac{ \alpha^{n+1} - \beta^{n+1} } { \sqrt{5} } $$
