Rekursionsformeln

Rekursionsformeln beschreiben Folgen oder Sequenzen, deren n-te Glied durch eine Beziehung zu vorherigen Gliedern festgelegt wird. Typisch sind lineare Rekursionen mit konstanten Koeffizienten; auch nicht-lineare oder nicht konstan­tente Koeffizienten sind möglich. Eine gängige Form ist a_n = c1 a_{n-1} + c2 a_{n-2} + ... + ck a_{n-k} + f(n) für n ≥ k, mit den Anfangswerten a_0, ..., a_{k-1}. Die Folge wird durch diese Anfangswerte eindeutig bestimmt.

Bei homogenen Rekursionsgleichungen (f(n) = 0) mit konstanten Koeffizienten liefert das charakteristische Polynom r^k - c1 r^{k-1} - ... - ck = 0. Die allgemeine Lösung folgt als Linearkombination von r_i^n, wobei bei mehrfachen Wurzeln passende Polynome multipliziert werden. Bei nicht-homogenen Gleichungen erhält man eine besondere Lösung und addiert die allgemeine Lösung der entsprechenden homogenen Gleichung. Generating-Function-Methoden (Erzeugende Funktionen) wandeln die Rekursion in eine Funktion A(x) = sum a_n x^n um und liefern oft geschlossene oder erklärende Darstellungen.

Anwendungsgebiete finden Rekursionsformeln vor allem in der Algorithmusanalyse, Kombinatorik und Informatik. Ein bekanntes Beispiel ist die Fibonacci-Folge F_n = F_{n-1} + F_{n-2} mit F_0 = 0, F_1 = 1. Dividier- und Eroberungsrekursionen wie T(n) = a T(n/b) + f(n) entstehen in der Algorithmusanalyse; je nach Wert von a, b und f(n) ergeben sich verschiedene asymptotische Klassen (Master-Theorem). Allgemein bestimmen die Anfangswerte die eindeutige Sequenz; bei einigen Rekursionen existiert keine geschlossene Form, sodass man nur asymptotische Abschätzungen oder numerische Berechnungen nutzt.