Lineare Rekursion mit konstanten Koeffizienten

Studium

a_n = p\,a_{n-1} + q\,a_{n-2} \;\Rightarrow\; a_n = c_1 \lambda_1^{n} + c_2 \lambda_2^{n}

Voraussetzung: $p, q \in \mathbb{R},$ $q \neq 0,$ $\lambda_1 \neq \lambda_2$ $Lösungen von$ $\lambda^2 = p\lambda + q,$ $n \geq 2$ $in der Rekursion$

$a_n$: n-tes Folgenglied
$p, q$: konstante Koeffizienten der Rekursion
$\lambda_1, \lambda_2$: verschiedene Lösungen der charakteristischen Gleichung λ² = pλ + q, eventuell komplex
$c_1, c_2$: Konstanten, die aus den Startwerten a₀ und a₁ bestimmt werden

Eine lineare Rekursion zweiter Ordnung löst man über die Nullstellen der charakteristischen Gleichung λ² = pλ + q.

Erklärung

Eine lineare Rekursion zweiter Ordnung mit konstanten Koeffizienten hat die Form $a_n = p\,a_{n-1} + q\,a_{n-2}$ . Mit zwei Startwerten $a_0$ , $a_1$ ist die Folge eindeutig festgelegt. Gesucht ist eine explizite Formel für $a_n$ .

Lösungsweg:

Ansatz $a_n = \lambda^n$ einsetzen und durch $\lambda^{n-2}$ teilen. Es entsteht die charakteristische Gleichung $\lambda^2 = p\lambda + q$ , also $\lambda^2 - p\lambda - q = 0$ .
Die Nullstellen $\lambda_1, \lambda_2$ bestimmen, z.B. mit der pq-Formel.
Verschiedene Nullstellen: $a_n = c_1 \lambda_1^n + c_2 \lambda_2^n$ . Doppelte Nullstelle $\lambda$ : $a_n = (c_1 + c_2 n)\,\lambda^n$ .
$c_1$ und $c_2$ aus den Startwerten $a_0$ und $a_1$ bestimmen (lineares Gleichungssystem).

Warum das funktioniert: Mit zwei Lösungen ist auch jede Linearkombination eine Lösung (Linearität), und zwei Konstanten reichen, um beliebige Startwerte zu treffen. Bei komplexen Nullstellen $\lambda_{1,2} = r\,e^{\pm i\theta}$ kann man reell als $a_n = r^n \left(c_1 \cos(n\theta) + c_2 \sin(n\theta)\right)$ schreiben.

Das Verfahren überträgt sich auf Ordnung $k$ : Die charakteristische Gleichung hat dann Grad $k$ , und eine $m$ -fache Nullstelle liefert die Terme $\lambda^n, n\lambda^n, \ldots, n^{m-1}\lambda^n$ .

Beispiele

Verschiedene Nullstellen: $a_n = 5a_{n-1} - 6a_{n-2}$ mit $a_0 = 1$ , $a_1 = 4$ .

Charakteristische Gleichung: $\lambda^2 - 5\lambda + 6 = 0$ , also $\lambda_1 = 2$ , $\lambda_2 = 3$ . Aus $c_1 + c_2 = 1$ und $2c_1 + 3c_2 = 4$ folgt $c_1 = -1$ , $c_2 = 2$ :

a_n = 2 \cdot 3^n - 2^n

Probe: Rekursiv ist $a_2 = 5 \cdot 4 - 6 \cdot 1 = 14$ und $a_3 = 5 \cdot 14 - 6 \cdot 4 = 46$ . Die Formel liefert $2 \cdot 9 - 4 = 14$ und $2 \cdot 27 - 8 = 46$ .

Doppelte Nullstelle: $a_n = 4a_{n-1} - 4a_{n-2}$ mit $a_0 = 1$ , $a_1 = 4$ . Aus $\lambda^2 - 4\lambda + 4 = (\lambda - 2)^2$ folgt $a_n = (c_1 + c_2 n)\,2^n$ . Startwerte: $c_1 = 1$ und $(1 + c_2) \cdot 2 = 4$ , also $c_2 = 1$ :

a_n = (1 + n)\,2^n

Probe: $a_2 = 4 \cdot 4 - 4 \cdot 1 = 12 = 3 \cdot 4$ .

Typische Fehler

Vorzeichen in der charakteristischen Gleichung. Aus $a_n = 5a_{n-1} - 6a_{n-2}$ wird $\lambda^2 - 5\lambda + 6 = 0$ , nicht $\lambda^2 + 5\lambda - 6 = 0$ .
Bei doppelter Nullstelle nur $c\,\lambda^n$ ansetzen. Dann reicht eine Konstante nicht für zwei Startwerte. Der Faktor $n$ beim zweiten Term ist nötig.
Konstanten mit $a_1, a_2$ statt $a_0, a_1$ bestimmen, aber $n$ ab $0$ zählen. Die Gleichungen für $c_1, c_2$ müssen zu den Indizes der gegebenen Startwerte passen.

Lineare Rekursion mit konstanten Koeffizienten