9.1.10 Bemerkung. Statt für die Glieder einer Folge eine direkte Berechnungsvorschrift anzugeben, kann man sie auch rekursiv definieren. Dazu gibt man die ersten paar Folgenglieder explizit an und stellt für die restlichen Folgenglieder klar, wie diese aus den bis dahin bekannten Folgengliedern berechnet werden können.

9.1.11 Beispiel.

1.

Wir betrachten die Folge (a_n)_n∈ℕ , mit a_n = 2n. Rekursiv lässt sie sich beispielsweise wie folgt definieren:

Denn es gilt

Damit ergeben sich die ersten zehn Folgenglieder als

2.

Wir betrachten die Folge (a_n)_n≥−4 mit der rekursiven Berechnungsvorschrift

In Worten besagt die Rekursionsvorschrift, dass die Folge bei −17 startet und jedes andere Folgenglied genau 5 mehr ist als das vorhergehende. Damit ergeben sich die folgenden Werte:

3.

Wir betrachten die rekursiv definierte Folge (b_n)_n∈ℕ , mit

In Worten bedeutet die Rekursionsvorschrift Folgendes: Das erste Folgenglied ist 1 und jedes andere Folgenglied ist genau das Doppelte des vorhergehenden Gliedes. Wir geben die ersten zehn Folgenglieder an.

Das vierte Folgenglied lässt sich beispielsweise wie folgt berechnen:

Man kann die einzelnen Folgenglieder auch nacheinander berechnen.

Wir hätten auch ohne große Mühe eine direkte Berechnungsvorschrift angeben können, denn es gilt

für alle n ∈ ℕ.

4.

Die rekursiv definierte Folge (f_n)_n∈ℕ , mit

ist unter dem Namen Fibonacci-Folge bekannt. In Worten ausgedrückt, sind die ersten beiden Folgenglieder als 1 festgelegt und jedes andere Folgenglied entspricht der Summe der beiden vorhergehenden Gliedern. Wir geben wieder die ersten zehn Folgenglieder an.

Auch für diese Folge lässt sich eine direkt Berechnungsvorschrift angeben. Da diese Vorschrift aber recht kompliziert und alles andere als naheliegend ist, gibt man in der Regel die rekursive Definition an.

5.

Wir betrachten nun die rekursiv definierte Folge (a_n)_n∈ℕ , mit

In Worten ist das n-te Folgenglied also das Produkt aller natürlichen Zahlen von 1 bis n. Daraus ergibt sich die direkte Berechnungsvorschrift.

Man schreibt für a_n auch n! und nennt die entsprechende Zahl n Fakultät. Diese Folge spielt in der Kombinatorik (einem Teilgebiet der Mathematik) eine wichtige Rolle.

Die ersten zehn Folgenglieder sehen wie folgt aus:

9.1.12 Aufgabe.

1.

Betrachte die Folge (a_n)_n∈ℕ , mit

Berechne die ersten zehn Folgenglieder und gib eine direkte Berechnungsvorschrift an.

2.

Betrachte die Folge (a_n)_n≥0, mit

Berechne die ersten zehn Folgenglieder. Die Glieder dieser Folge kommen mit wachsendem Index einer gewissen rationalen Zahl immer näher. Wie lautet diese Zahl? (Man bezeichnet diese Zahl dann auch als Grenzwert der Folge. Dazu später mehr.)

3.

Betrachte die rekursiv definierte Folge

aus Beispiel 9.1.11. Dort haben wir behauptet, dass

gilt. Dies wollen wir nun auch beweisen.

(a)

Zeige, dass die Formel b_n = 2ⁿ⁻¹ für n = 1 gilt.

(b)

Zeige, dass die Formel für ein beliebiges n ≥ 2 gilt, wenn wir voraussetzen, dass die Formel für n−1 gilt.

(c)

Folgere mit Hilfe dieser beiden Aussagen, dass die Formel für alle n ∈ ℕ gilt.

Diese Beweismethode nennt man vollständige Induktion. Sie ist eines der Grundwerkzeuge im Studium der Mathematik.

4.

Wenn du die obige Aufgabe gemeistert hast, kannst du auch versuchen, die in Beispiel 9.1.11 genannte Formel für die Glieder der rekursiv definierten Fibonacci-Folge

zu beweisen. Gehe dazu wie folgt vor:

(a)

Zeige, dass die Formel für n = 1 und n = 2 gilt.

(b)

Zeige, dass die Formel für ein beliebiges n ≥ 3 gilt, wenn wir voraussetzen, dass die Formel für n−1 und n−2 gilt.

(c)

Folgere mit Hilfe dieser beiden Aussagen, dass die Formel für alle n ∈ ℕ gilt.

Hinweis: die Zahlen

sind Lösungen der quadratischen Gleichung  x² −x−1 = 0.