Berechnung der expliziten Darstellung einer Folge aus einer Rekursion

Aus ÖMO Wiki

Wechseln zu: Navigation, Suche
Beweis fehlt.png Für diesen Satz fehlt noch ein Beweis!

Oft steht man vor dem Problem, mit einer Folge zu arbeiten, die nur rekursiv gegeben ist. Speziell das Ausrechnen bzw. die Untersuchung großer Werte ist dann sehr mühsam. Aber es gibt ein Verfahren, mit dem man für viele Folgen relativ einfach eine explizite Darstellung finden kann (am Ende dieser Seite wird das Verfahren noch an Hand der Fibonacci-Zahlen praktisch vorgeführt).

Vorgehensqweise

Gegeben sei eine Folge \langle a_n \rangle mit r vorgegebenen Startwerten a_0,\ a_1,\ \ldots,\ a_r, die wie folgt definiert ist (alle bk sind reelle Zahlen):

a_{n+r+1} = b_r a_{n+r} + b_{r-1} a_{n+r-1} + b_{r-2} a_{n+r-2} + \ldots + b_1 a_{n+1} + b_0 a_n

Es handelt sich dabei um eine ganz allgemeine Darstellung einer linearen rekursiven Folge. Sie kann von belibig vielen (r) früheren Werten abhängen, aber das nur linear. D.h., dass keine Elemente der Folge in einer höheren Potenz als 1 vorkommen. Beispiele für nichtlineare Terme wären etwa {a_n}^2 oder anan − 1.

Macht man nun den Ansatz

a_n = c \cdot q^n

und setzt ein, so erhält man:

c q^{n+r+1} = b_r c q^{n+r} + \ldots + b_0 c q^n

Man kann auf beiden Seiten durch cqn dividieren und erhält somit

q^{r+1} = b_r q^{r} + b_{r-1}q^{r-1} + \ldots + b_1q + b_0

also eine "normale" Gleichung in q vom Grad r+1, die auch charakteristische Gleichung genannt wird. Diese Gleichung hat r+1Lösungen, die wir mit q_1,\ q_2,\ \ldots,\ q_{r+1} bezeichnen. Jede für sich ist eine Lösung der Rekursion, aber auch ihre Summe ist eine (nämlich die allgemeine) Lösung (dass die Summe ebenfalls Lösung ist folgt aus der Linearität). Also lautet die allgemeine Lösung:

a_n = c_1 {q_1}^n + c_2 {q_2}^n + \ldots + c_{r+1} {q_{r+1}}^n

mit beliebigen Konstanten c_1,\ \ldots,\ c_{r+1}, die durch Einsetzen der gegebenen Anfangswerte a_0, \ldots a_r bestimmt werden können.


Beispiel: Die Fibonacci-Zahlen

Die Fibonacci-Zahlen sind definiert durch:

a_0 = 1,\ a_1 = 1,\ a_{n+2} = a_{n+1} + a_n

es liegt also der Fall r = 1 vor.

Macht man nun den Ansatz an = cqn, so erhält man die charakteristische Gleichung

q2 = q + 1

mit den beiden Lösungen _ q_1 = \frac{1-\sqrt{5}}{2} \qquad q_2 = \frac{1+\sqrt{5}}{2}

Also haben die Fibonacci-Zahlen vorerst die Gestalt

a_n = c_1 \left( \frac{1-\sqrt{5}}{2} \right)^n + c_2 \left( \frac{1+\sqrt{5}}{2} \right)^n

Es bleiben noch die Konstanten c_1,\ c_2 aus den Anfangswerten zu berechnen:

\begin{matrix} a_0 = 1 & \Rightarrow & c_1 + c_2 = 1 \\ a_1 = 1 & \Rightarrow & c_1 \left( \frac{1-\sqrt{5}}{2} \right) + c_2 \left( \frac{1+\sqrt{5}}{2} \right) = 1 \end{matrix}

Aus der ersten Gleichung folgt sofort c2 = 1 − c1. Setzt man das in die zweite Gleichung ein so erhält man:

\begin{matrix} c_1 \left( \frac{1-\sqrt{5}}{2} \right) + (1-c_1) \left( \frac{1+\sqrt{5}}{2} \right) & = & 1 \\ c_1 \left( \frac{1-\sqrt{5}}{2} - \frac{1+\sqrt{5}}{2} \right) & = & 1 - \frac{1+\sqrt{5}}{2} \\ -c_1 \sqrt{5} & = & - \frac{\sqrt{5}-1}{2} \\ c_1 & = & -\frac{1-\sqrt{5}}{2\sqrt{5}} \\ c_2 & = & \frac{\sqrt{5}+1}{2} \end{matrix}

Damit lautet die explizite Darstellung der Fibonacci-Zahlen:

a_n = \frac{1}{\sqrt{5}} \left[ \left( \frac{1+\sqrt{5}}{2} \right)^{n+1} - \left( \frac{1-\sqrt{5}}{2} \right)^{n+1} \right]
Wikipedia: Lineare Differenzengleichung
Von „http://www.oemo.at/wiki/index.php/Berechnung_der_expliziten_Darstellung_einer_Folge_aus_einer_Rekursion“
Persönliche Werkzeuge