Lineare Rekursionsgleichungen

Definition

Eine Gleichung der Form

$$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\ldots+c_{k}a_{n-k}+b_{k}\left(n\geq k\right)$$

mit den Anfangsbedingungen

$$a_{0}=b_{0},\ a_{1}=b_{1},\ \ldots\ ,\ a_{k-1}=b_{k-1}$$

heißt lineare Rekursionsgleichung (RG) $k$-ter Ordnung. Für $b_{k}=0$ heißt die Gleichung homogen, sonst inhomogen. Ziel ist es einen geschlossenen Ausdruck zu finden.

lineare Rekursionsgleichung 1. Ordnung

Eine (inhomogene) lineare RG 1.Ordnung

$$a_{0}=b_{0},\; a_{n}=c_{1}a_{n-1}+b_{1}\quad\left(n\geq1\right)$$

hat die Lösung

$$a_{n}=\left\{ \begin{array}{cc} c_{1}^{n}b_{0} & \left(b_{1}=0\ri... ...n}b_{0}+\frac{c_{1}^{n}-1}{c_{1}-1}b_{1} & \left(sonst\right)\end{array}\right.$$

lineare Rekursionsgleichung 2. Ordnung

Eine homogene lineare RG 2. Ordnung hat

$$a_{0}=b_{0},\; a_{1}=b_{1},\; a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}\left(n\geq2\right)$$

• bei $c_{1}^{2}+4c_{2}>0$ die Reelle Lösung:
  $$a_{n}=A\alpha^{n}-B\beta^{n}$$
  wobei $\alpha,\beta$ die zwei (verschiedenen) Lösungen der Gleichung
  $t^{2}-c_{1}t-c_{2}=0$ sind
  $$\alpha=\frac{c_{1}}{2}+\sqrt{\frac{c_{1}^{2}}{4}+c_{2}}\quad\beta=\frac{c_{1}}{2}-\sqrt{\frac{c_{1}^{2}}{4}+c_{2}}$$
  und
  $$A=\frac{b_{1}-b_{0}\beta}{\alpha-\beta}\quad B=\frac{b_{1}-b_{0}\alpha}{\alpha-\beta}$$

• bei $c_{1}^{2}+4c_{2}=0$ die Reelle Lösung:
  $$a_{n}=\left(nb_{1}-\left(n-1\right)\alpha b_{0}\right)\alpha^{n-1}\quad\alpha=\frac{c_{1}}{2}$$

• bei $c_{1}^{2}+4c_{2}<0$ die komplexe Lösungen. Formeln siehe bei $c_{1}^{2}+4c_{2}>0$.

Fibonacci-Folge

Die Fibonacci-Folge

$$F_{0}=0,\; F_{1}=1,\; F_{n}=F_{n-1}+F_{n-2}\left(n\geq2\right)$$

hat die Lösung:

$$F_{n}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{n}$$

• $F_{n+1}=\sum_{k=0}^{n}\left(\begin{array}{c} n-k\\ k\end{array}\right)$
• $F_{2n-1}=F_{n-1}^{2}+F_{n}^{2}$
• $F_{2n}=F_{n}\left(2F_{n-1}+F_{n}\right)$
• $\left(\begin{array}{cc} 1 & 1\\ 1 & 0\end{array}\right)^{n}=\left(\begin{arra... ...c} F_{n+1} & F_{n}\\ F_{n} & F_{n-1}\end{array}\right)\quad\left(n\geq1\right)$