Munterbunt

Lineare Rekursion

Übersicht > Folgen und Reihen > Iteration und Rekursion > Lineare Rekursion

Aufgabe

Die Folge $F(0)$ , $F (1)$ , $F (2)$ , ... ist rekursiv definiert durch

F(n) = 2F (n - 1)+ 3F(n - 2)

F (0) = 7, F (1) = 13

Gesucht ist eine explizite Formel für $F(n)$ .

Lösung

Die Folge wächst exponentiell, Ansatz $F(n) = a.qn$ . Einsetzen in der Rekursionsgleichung liefert $q2- 2q - 3 = 0,q1 = 3,q2 = - 1$ . Linearkombination der beiden Lösungen liefert

F (n) = 5.3n + 2.(-1)n