Explizite Lösung rekursiver Formeln
Wenn eine Folge durch eine rekursive Formel definiert ist, kann es schwierig sein, ein beliebiges Glied zu berechnen, da man immer die vorherigen kennen muss. Deshalb sucht man oft nach einer expliziten Lösung, bei der jedes Glied direkt aus \( \large n \) berechnet werden kann.
Von rekursiv zu explizit
Eine gängige Methode ist es, die ersten Glieder aufzuschreiben und zu versuchen, ein Muster zu finden. Oft zeigen die ersten Berechnungen eine Beziehung, die verallgemeinert werden kann.
Beispiel 1
Wir betrachten die Folge
$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$
Die ersten Werte sind
$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16 $$
Das Muster ist klar: jedes Glied ist eine Potenz von 2. Die explizite Formel ist
$$ \large a_{n} = 2^n $$
Beispiel 2
Wir betrachten die Folge
$$ \large a_{n} = 2 \cdot a_{n-1} + 1, \quad a_{0} = 1 $$
Die ersten Werte sind
$$ \large a_{1} = 3, \quad a_{2} = 7, \quad a_{3} = 15, \quad a_{4} = 31 $$
Hier sehen wir das Muster: \( \large a_{n} = 2^{\,n+1} - 1 \). Dies kann durch Induktion oder durch „Auspacken der Rekursion“ Schritt für Schritt bewiesen werden.
Die Rekursion auspacken
Anstatt nur das Muster zu erraten, kann man versuchen, mehrmals in der Formel zu substituieren. Zum Beispiel:
$$ \large a_{n} = 2 \cdot a_{n-1} + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2 \cdot (2 \cdot a_{n-2} + 1) + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2^2 \cdot a_{n-2} + 2 + 1 \quad \Leftrightarrow $$
$$ \large a_{n}= 2^3 \cdot a_{n-3} + 2^2 + 2 + 1 $$
Wenn wir dieses Muster bis zu \( \large a_{0} = 1 \) fortsetzen, erhalten wir
$$ \large a_{n} = 2^n \cdot a_{0} + (2^n - 1) $$
Da \( \large a_{0} = 1 \), wird das Ergebnis
$$ \large a_{n} = 2^n + 2^n - 1 \quad \Leftrightarrow $$
$$ \large a_{n} = 2^{\,n+1} - 1 $$
Beispiel einer Rekursion 2. Ordnung
Wir betrachten nun eine Folge, die von den zwei vorherigen Gliedern abhängt:
$$ \large a_{n} = a_{n-1} + a_{n-2}, \quad a_{0} = 2, \quad a_{1} = 3 $$
Die ersten Glieder sind:
$$ \large a_{2} = 5, \quad a_{3} = 8, \quad a_{4} = 13, \quad a_{5} = 21, \ldots $$
Um eine explizite Formel zu finden, verwenden wir die Methode der charakteristischen Wurzeln. Wir vermuten eine Lösung der Form:
$$ \large a_{n} = r^n $$
Warum gerade diese Vermutung?
Die Rekursion ist linear und hat konstante Koeffizienten.
Wenn ein Glied immer eine Linearkombination einer festen Anzahl vorheriger Glieder ist, liegt es nahe, eine exponentielle Form \( \large r^n \) zu versuchen. Wenn wir diese Vermutung einsetzen, reduziert sich die gesamte Rekursion auf eine Gleichung in \( \large r \), die nicht von \( \large n \) abhängt.
Das bedeutet, dass die gesamte Rekursion durch eine geometrische Folge erfüllt werden kann, bei der das Verhältnis zweier aufeinanderfolgender Glieder konstant ist.
Andere Vermutungen, wie \( \large n^\alpha \), könnten die Rekursion für alle \( \large n \) nicht erfüllen.
Eingesetzt in die Rekursion ergibt dies:
$$ \large r^n = r^{n-1} + r^{n-2} $$
Teilen wir durch \( \large r^{\,n-2} \) (für \( \large r \neq 0 \)), so erhalten wir
$$ \large r^2 = r + 1 $$
Dies nennt man die charakteristische Gleichung. Sie kann umgeschrieben werden zu:
$$ \large r^2 - r - 1 = 0 $$
Mit der Mitternachtsformel finden wir die Diskriminante:
$$ \large \Delta = (-1)^2 - 4 \cdot 1 \cdot (-1) \quad \Leftrightarrow $$
$$ \large \Delta = 1 + 4 \quad \Leftrightarrow $$
$$ \large \Delta = 5 $$
Daraus ergibt sich die Quadratwurzel von 5. Die Lösungen sind:
$$ \large r_1 = \frac{1 + \sqrt{5}}{2}, \quad r_2 = \frac{1 - \sqrt{5}}{2} $$
Damit ist die allgemeine Lösung
$$ \large a_{n} = C_1 \cdot r_1^n + C_2 \cdot r_2^n $$
Wir bestimmen die Konstanten aus den Anfangsbedingungen:
$$ \large a_{0} = 2 = C_1 + C_2 $$
$$ \large a_{1} = 3 = C_1 \cdot r_1 + C_2 \cdot r_2 $$
Daraus ergibt sich:
$$ \large C_1 = \frac{1 + \sqrt{5}}{\sqrt{5}}, \quad C_2 = \frac{\sqrt{5} - 1}{\sqrt{5}} $$
Die explizite Formel wird also:
$$ \large a_{n} = \frac{1 + \sqrt{5}}{\sqrt{5}} \cdot \left(\frac{1 + \sqrt{5}}{2}\right)^n \;+\; \frac{\sqrt{5} - 1}{\sqrt{5}} \cdot \left(\frac{1 - \sqrt{5}}{2}\right)^n $$
Mit dieser Formel kann man jedes Glied direkt berechnen. Zum Beispiel für \( \large n = 5 \):
$$ \large a_{5} = 21 $$
Zusammenfassung
Eine explizite Lösung ermöglicht es, direkt zum Glied Nummer \( \large n \) zu springen, ohne alle vorherigen zu berechnen. Man findet die Formel oft, indem man ein Muster beobachtet oder die Rekursion auspackt. In fortgeschritteneren Fällen, wie bei Rekursionen 2. Ordnung, kann man die Methode der charakteristischen Wurzeln verwenden. Viele rekursive Formeln können so in eine einfache explizite Form umgeschrieben werden, die sowohl Einblick in die Struktur gibt als auch die Berechnung erleichtert.