Charakteristisches Polynom

Sei

$$(\ast)\ \text{f}_n = \text{f}_{n-1} + \text{f}_{n-2} \text{ f\uml {u}r } n \geq 2,\ \text{f}_1=1,\ \text{f}_0=0$$

(lineare homogene Rekursionsgleichung zweiter Ordnung)
Setze $\text{f}_n=a^n$ für ein unbekanntes a.
aⁿ-a^n-1-a^n-2=0; da hier $a \neq 0$: a²-a-1=0; $a_{1/2}=\frac{1\pm\sqrt{5}}{2}$
a₁ und a₂ Lösungen von ($\ast$), dann auch $\text{f}_n=c_1a_1^n+c_2a_2^n$ eine Lösung für ($\ast$).
$\text{f}_1=1$ und $\text{f}_0=0$ liefern zwei Gleichungen für c₁ und c₂.
Lösung: $\text{f}_n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$