Rekursive Folgen PDF

Preview

Summary

Download Rekursive Folgen PDF

Description

2 Rekursiv definierte Folgen Wenn man die Konvergenz von rekursiv definierten Folgen zeigen soll, würde ich immer wie folgt vorgehen: 1. Man nimmt zuerst an, dass die Folge konvergent wäre und berechnet mit Hilfe von lim n →∞ an = lim n →∞ an +1 = a den möglichen Grenzwert der Funktion. 2. Durch die Berechnung des möglichen Grenzwertes haben wir jetzt eine mögliche obere (oder untere) Schranke der rekursiv definierten Folge gefunden und können die Beschränktheit der Funktion mittels vollständiger Induktion zeigen. 3. Als letztes zeigt man dann noch die entsprechende Monotonie. Wenn die Folge nach oben beschränkt ist, zeigt man, dass die Folge monoton wachsend ist, wenn sie nach unten beschränkt ist, zeigt man, dass die Folge monoton fallend ist. Dann folgt die Konvergenz der Folge mit dem Satz: Eine monoton wachsende (fallende) Folge ist genau dann konvergent, wenn sie nach oben (nach unten) beschränkt ist. Nun aber zu etlichen Beispielen: Beispiel 1: Zeige, dass die rekursiv definierte Folge an +1 :=

1 an + 1 mit dem Startwert a0 := 1 konvergiert. 2

Angenommen, die Folge konvergiert. Dann erhielten wir folgenden Grenzwert: 1 1 a = a + 1 ⇔ a = 1⇒ a = 2 2 2 Setzt man ein paar Werte ein, so stellt man schnell fest, dass die Folge wohl nach oben durch 2 beschränkt ist.

• Beschränktheit Wir zeigen an ≤ 2 . Dies kann man sehr gut mit Hilfe von vollständiger Induktion zeigen, denn wir müssen es ja für alle n zeigen. Induktionsanfang: Für n=0 erhalten wir a 0 = 1 ≤ 2 . Dies ist also wahr. Induktionsschritt: Von n auf n+1: Wir zeigen an +1 ≤ 2 unter der Induktionsvoraussetzung (IV), dass an ≤ 2 für ein n schon bewiesen ist.

an +1 =

( IV ) ! 1 1 an + 1 ≤ • 2 + 1 = 2 2 2

Damit haben wir also die Beschränktheit der Folge nach oben durch 2 gezeigt.

• Monotonie Wir müssen zeigen, dass die Folge monoton wachsend ist, dass also an+1 ≥ an gilt. Dies ist gleichbedeutend zu an +1 − an ≥ 0 . 1 1 − a + 2 2 − an an +1 − an = an + 1 − an = − an + 1 = n = > 0 2 2 2 2 da a"n ≤2 Damit folgt die Konvergenz der Folge gegen den Grenzwert 2. (Anmerkung: Natürlich kann man jede andere obere Schranke nehmen, z.B. auch 3, aber durch das vorherige Ausrechnen des möglichen Grenzwerts kennen wir ja schon mal eine sehr gute Schranke.) Beispiel 2: Wir betrachten nun die Folge an +1 := ln(1 + an ) mit Startwert a1 := 1 . Die Vorgehensweise ist analog wie oben (bei allen folgenden Beispielen). Möglicher Grenzwert:

a = ln(1 + a) ⇔ ea = 1 + a Dies ist nur für a = 0 erfüllt. • Beschränktheit Wir zeigen an ≥ 0 . Wir zeigen also, dass die Folge nach unten durch 0 beschränkt ist. Auch hier wieder mit Induktion: Induktionsanfang: Für n=1 erhalten wir a1 = 1 ≥ 0 . Dies ist also wahr. Induktionsschritt: Von n auf n+1: Wir zeigen an+1 ≥ 0 unter der Induktionsvoraussetzung (IV), dass an ≥ 0 für ein n schon bewiesen ist. (IV )

! an +1 = ln(1+ an ) ≥ ln(1) = 0 Damit haben wir also die Beschränktheit der Folge nach unten durch 0 gezeigt.

• Monotonie Wir zeigen, dass die Folge monoton fallend ist. Dass also an +1 ≤ an gilt bzw. an +1 − an ≤ 0 . Mit ln(1 + x) ≤ x ∀x ≥ −1 ergibt sich an +1 = ln(1+ an ) < an und damit die Behauptung. Damit folgt auch die Konvergenz der rekursiv definierten Folge gegen den Grenzwert 0.

Beispiel 3: Wir betrachten nun die Folge an +1 := 2 + an mit Startwert a1 := 2 . Möglicher Grenzwert ergibt sich durch Grenzwertübergang lim n→∞ a n = lim n→∞ a n+1 = a :

an +1 := 2 + an a = 2 + a ⇔ a² = 2 + a ⇔ a² − a − 2 = 0 ⇒ a1 = 2 ∨ a 2 = −1 (Dieser Grenzwert scheidet aber aus, da die Wurzel nur positive Werte annimmt.) • Beschränktheit Wir behaupten nun, dass die Folge nach oben durch 2 beschränkt ist. Zeigen also wieder mit Induktion an ≤ 2 . Induktionsanfang: Für n=1 ergibt sich die wahre Aussage a 1 = 2 ≤ 2 . Induktionsschritt: Von n auf n+1 Wir zeigen an+1 ≤ 2 unter der Induktionsvoraussetzung (IV), dass an ≤ 2 für ein n bewiesen ist. ( IV )

! an +1 := 2 + an ≤

2+2 = 4 = 2

Damit ist die Beschränktheit gezeigt.

• Monotonie Wir zeigen, dass die Folge monoton wachsend ist, also an +1 ≤ an bzw. an+1 − an ≤ 0 . an +1 ≤ an 2 + an ≤ an ⇔ 2 + an ≤ an ² ⇔ 0 ≤ an ² − an + 2 1 9 0 ≤ ( an − )² − Da an ≤ 2 gilt dies offensichtlich. 2 4 Damit haben wir die Konvergenz der Folge gegen 2 gezeigt.

Beispiel 4: 1 Nun betrachten wir die Folge an+1 = ( an ² + 2) mit dem Startwert 1 ≤ a0 ≤ 2 . 3 Wäre die Folge konvergent, so wäre der Grenzwert:

1 1 2 a = (a ² + 2) = a ² + 3 3 3 1 2 ⇔ a² + − a = 0 ⇔ a² − 3a + 2 = 0 3 3 ⇒ a1 = 2 ∨ a 2 = 1 1 Der erste Grenzwert scheidet aus, da an +1 = (an ² + 2) ≥ 0 für alle Startwerte. 3

• Beschränktheit Zeige also, dass die Folge nach oben durch 2 beschränkt ist. Wir müssen also a n ≤ 2 zeigen. Induktionsanfang: Für n=0 erhalten wir a 0 ≤ 2 , da 1≤ a0 ≤ 2 . Induktionsschritt: Von n auf n+1 Wir müssen zeigen, dass an+1 ≤ 2 unter der Induktionsvoraussetzung (IV), dass wahr ist. (IV ) ! 1 1 1 an +1 = ( an ² + 2) ≤ (2² + 2) = (3 + 2) = 2 3 3 3

• Monotonie Wir zeigen, dass die rekursiv definierte Folge monoton wachsend ist. 1 1 2 an +1 = ( an ² + 2) ≥ an ⇔ an ² + − an ≥ 0 ⇔ an ² − an + 2 ≥ 0 3 3 3 1 7 ⇔ (an − )² + ≥ 0 2 4 Wir haben also gerade die Konvergenz der Folge gezeigt.

Beispiel 5: Wir betrachten nun die Folge an +1 = 3 −

2 . an

Wäre die Folge konvergent, so gelte: 2 ⇔ a ² = 3a − 2 ⇔ a ² − 3 a + 2 = 0 a ⇒ a1 = 2 ∨ a2 = 1

a = 3−

Das Ganze führt also wieder auf Beispiel 4. Beispiel 6: Sei a1 = A mit A ∈ (0,1) . Mit anderen Worten 0 < a1...