Folgen und rekursive Formeln

Eine Folge ist eine geordnete Liste von Zahlen, bei der jedes Element einen bestimmten Platz hat. Eine Folge kann entweder durch eine explizite Formel oder durch eine rekursive Formel beschrieben werden.

Wenn eine Folge rekursiv definiert wird, hängt das nächste Glied von einem oder mehreren vorherigen Gliedern ab.

Beispiel für eine einfache rekursive Folge

Wir können eine Folge definieren, bei der jedes Glied doppelt so groß ist wie das vorherige:

$$ \large a_{n} = 2 \cdot a_{n-1}, \quad a_{0} = 1 $$

Hier ist $ \large a_{0} = 1 $ der Startpunkt. Aus der Formel erhalten wir

$$ \large a_{1} = 2, \quad a_{2} = 4, \quad a_{3} = 8, \quad a_{4} = 16, \ldots $$

Rekursive Formel

In einer rekursiven Formel wird ein Glied aus vorherigen Gliedern beschrieben. Um zu beginnen, muss man einen oder mehrere Startwerte kennen, die Anfangsbedingungen genannt werden.

Rekursion erster Ordnung

Eine Rekursion erster Ordnung bedeutet, dass jedes Glied nur vom vorherigen abhängt. Ein Beispiel ist

$$ \large a_{n} = 3 \cdot a_{n-1}, \quad a_{0} = 2 $$

Hier wird jedes Glied im Vergleich zum vorherigen mit 3 multipliziert. Die Folge lautet

$$ \large 2, \; 6, \; 18, \; 54, \ldots $$

Rekursion zweiter Ordnung

Eine Rekursion zweiter Ordnung bedeutet, dass jedes Glied von den beiden vorherigen abhängt. Das bekannteste Beispiel ist die Fibonacci-Folge:

$$ \large F_{n} = F_{n-1} + F_{n-2}, \quad F_{0} = 0, \quad F_{1} = 1 $$

Hier ist jedes Glied die Summe der beiden vorherigen. Die Folge beginnt so:

$$ \large 0, \; 1, \; 1, \; 2, \; 3, \; 5, \; 8, \; 13, \ldots $$

Es gibt viele weitere Beispiele für Rekursionen zweiter Ordnung. Hier ist eines, bei dem jedes Glied gebildet wird, indem man das vorherige mit 2 multipliziert und das vorvorherige abzieht:

$$ \large a_{n} = 2 \cdot a_{n-1} - a_{n-2}, \quad a_{0} = 1, \quad a_{1} = 2 $$

Setzen wir die ersten Werte ein, so erhalten wir

$$ \large a_{2} = 3, \quad a_{3} = 4, \quad a_{4} = 5, \quad a_{5} = 6, \ldots $$

In diesem Fall ergibt die Rekursion eine einfache arithmetische Folge, auch wenn die ursprüngliche Formel komplizierter aussieht.

Explizite Formel

Hier kann man tatsächlich eine explizite Formel finden, die die gesamte Folge direkt beschreibt:

$$ \large a_{n} = n + 1 $$

Dies zeigt, dass rekursive und explizite Formen oft eng miteinander verbunden sind. Eine scheinbar komplexe rekursive Definition kann eine sehr einfache explizite Formel verbergen.

Terminologie

Beim Arbeiten mit rekursiven Formeln werden einige feste Begriffe verwendet:

Anfangsbedingungen: die ersten Werte, die die Folge starten.
Rekursionsgrad: wie viele vorherige Glieder verwendet werden, um das nächste zu bestimmen (z. B. erster oder zweiter Ordnung).
Basis: die ersten Schritte der Definition, auf denen der Rest aufbaut.

Diese Begriffe tauchen in allen Arten von rekursiven Definitionen auf und erleichtern die systematische Arbeit mit ihnen.

Zusammenfassung

Rekursive Formeln sind nützlich, um Strukturen zu beschreiben, bei denen jedes neue Glied aus den vorherigen hervorgeht. Sie geben ein klares Bild der Beziehung zwischen den Zahlen, erfordern aber die Kenntnis der früheren Glieder, um fortzufahren. Oft kann man später eine explizite Formel finden, die eine schnellere direkte Berechnung ermöglicht.

Das Verständnis des Unterschieds zwischen Rekursionen erster und zweiter Ordnung und ihres Verhältnisses zu expliziten Lösungen ist ein wichtiger erster Schritt in der Arbeit mit rekursiven Methoden.