Zum Inhalt springen

Konvergenz rekursiver Folgen beweisen – „Mathe für Nicht-Freaks“

Aus Wikibooks

In diesem Kapitel werde ich dir zeigen, wie du Konvergenzbeweise für rekursive Folgen führen kannst. Hier werden wir eine gute Anwendung des Monotoniekriteriums kennenlernen.

Problemstellung

[Bearbeiten]

Nehme folgende Aufgabe:

Sei (an)n∈ℕ eine durch a0=0 und durch an+1=12an+12 rekursiv definierte Folge. Konvergiert diese Folge? Wenn ja, wie lautet der Grenzwert?

Die Anwendung der Epsilon-Definition der Konvergenz ist in dieser Aufgabe schwierig. Weil die Folge (an)n∈ℕ rekursiv definiert ist, können wir ihren Grenzwert nicht direkt ablesen. Auch sind im Allgemeinen Abschätzungen für den Term |a−an| mit einer reellen Zahl schwierig, weil wir keine explizite Form des Folgenglieds an kennen.

Lösungsstrategien

[Bearbeiten]

In diesem Kapitel werde ich dir die folgenden zwei Lösungswege präsentieren, um die Konvergenz einer Folge zu zeigen:

  1. Explizite Bildungsvorschriften: Man kann versuchen, eine explizite Bildungsvorschrift der gegebenen Folge zu bestimmen, um mit dieser das Konvergenzverhalten der Folge weiter zu untersuchen.
  2. Monotoniekriterium verwenden: Wenn die rekursiv gegebene Folge konvergieren sollte, kann man versuchen, das Monotoniekriterium anzuwenden. Nachdem die Konvergenz der Folge bewiesen wurde, kann man dieses Wissen nutzen, um den Grenzwert der Folge zu bestimmen.

Lösungsweg: Explizite Bildungsvorschrift finden

[Bearbeiten]

Eine mögliche Lösungsstrategie ist die, eine explizite Bildungsvorschrift von (an)n∈ℕ zu bestimmen.

Hier bietet es sich an, die ersten Folgenglieder rekursiv auszurechnen. Dies ist generell empfehlenswert, um ein Gefühl für das Konvergenzverhalten der Folge zu bekommen. Die ersten Folgeglieder lauten:

a0=0a1=12a0+12=12⋅0+12=12a2=12a1+12=12⋅12+12=34a3=12a2+12=12⋅34+12=78a4=12a3+12=12⋅78+12=1516⋮

Aufgrund dieser Liste der ersten Folgenglieder können wir vermuten, dass die Folge gegen 1 konvergiert. Für die explizite Bildungsvorschrift müssen wir eine Zuordnungsvorschrift n↦an finden. Wir suchen also einen Term f(x) für den gilt:

f(0)=0f(1)=12f(2)=34f(3)=78⋮

Wir sehen, dass der Nenner jeweils eine Potenz von 2 ist. Außerdem ist der Zähler jeweils die Vorgängerzahl des Nenners. Es ist also

f(0)=0=20−120f(1)=12=21−121f(2)=34=22−122f(3)=78=23−123⋮

Anhand dieser Beispiele liegt die Vermutung nahe, dass wir f(n)=2n−12n wählen können. Es sollte also gelten:

an=f(n)=2n−12n=1−12n=1−(12)n

Diese Vermutung müssen wir noch beweisen. Hier bietet sich wie in vielen anderen Beispielen die vollständige Induktion an. Im Induktionsanfang haben wir:

a0=0=1−1=1−(12)0

Den Induktionsschritt von n nach n+1 können wir nach Anwendung des Rekursionsschritts führen:

an+1=12an+12↓ Induktionsvoraussetzung=12⋅(1−(12)n)+12=12−(12)n+1+12=1−(12)n+1

Damit haben wir an=1−(12)n gezeigt. Nun können wir das Konvergenzverhalten mit den Mitteln untersuchen, die wir bereits kennengelernt haben. Beispielsweise haben wir bereits limn→∞(12)n=0 bewiesen und damit können wir die Grenzwertsätze anwenden, um die Konvergenz der Folge zu beweisen:

limn→∞an=limn→∞1−(12)n↓ Grenzwertsatz: limn→∞(an+bn)=limn→∞an+limn→∞bn=limn→∞1−limn→∞(12)n=1−0=1

Alternative Möglichkeit: Folge in Teleskopreihe umformen und Bildungsvorschrift berechnen

[Bearbeiten]

Die explizite Bildungsvorschrift einer rekursiven Folge kann manchmal sehr kompliziert sein. In diesem Fall gibt es eine andere Möglichkeit diese zu bestimmen. Diese Methode ist insbesondere dann möglich, wenn die rekursive Bildungsvorschrift die beiden vorherigen Glieder beinhaltet. Betrachten wir das Beispiel

a0=0, a1=1, an=12an−1+12an−2

Betrachten wir die Differenz zweier aufeinanderfolgender Glieder an und an−1, so erhalten wir

an−an−1=12an−1+12an−2−an−1=12an−2−12an−1=12(an−2−an−1)=−12(an−1−an−2)

Führen wir denselben Schritt erneut durch, so erhalten wir

an−an−1=−12(an−1−an−2)=−12(12an−2+12an−3−an−2)=−12(12an−3−12an−2)=(−12)2(an−2−an−3)

In jedem Schritt kommt also −12 als Vorfaktor hinzu. Nach insgesamt n−1 Schritten erhalten wir

an−an−1=(−12)n−1(a1−a0)⏟=1=(−12)n−1

Damit können wir nun noch nicht den Grenzwert berechnen, da wir „nur“ eine Bildungsvorschrift für an−an−1 und noch nicht für an haben. Diese erreichen wir, wenn wir die (Teleskop-)Summe über ak−ak−1 bilden:

∑k=1n(ak−ak−1)=an−a0=an

Auf der rechten Seite ergibt sich die geometrische Summe

∑k=1n(−12)k−1=∑k=0n−1(−12)k=1−(−12)n1−(−12)=1−(−12)n32=23(1−(−12)n)

Damit erhalten wir die explizite Darstellung

an=23(1−(−12)n)

Mit limn→∞(−12)n=0 und den Rechenregeln für Folgen gilt

limn→∞an=limn→∞23(1−(−12)n)=23(1−0)=23

Lösungsweg: Monotoniekriterium anwenden

[Bearbeiten]

Schritt 1: Beweis der Konvergenz

[Bearbeiten]

Was machen wir, wenn wir keine explizite Bildungsvorschrift der Folge finden? In manchen Fällen kann das Monotoniekriterium helfen. Dieses Kriterium lautet:

Jede beschränkte und monotone Folge konvergiert.

Dementsprechend reicht es aus, wenn wir die Beschränktheit und die Monotonie der Folge zeigen. Schauen wir uns zunächst die ersten Folgeglieder an, um eine Vermutung über die Eigenschaften der Folge zu bekommen:

a0=0a1=12a0+12=12⋅0+12=12a2=12a1+12=12⋅12+12=34a3=12a2+12=12⋅34+12=78a4=12a3+12=12⋅78+12=1516⋮

Die Folge scheint monoton zu steigen. Außerdem sieht es so aus, als ob die Folge nach oben durch 1 beschränkt ist.

Die Monotonie können wir induktiv beweisen. Hier zeigen wir zunächst im Induktionsanfang, dass a1≥a0 ist:

a1=12a0+12=12⋅0+12=12≥0=a0

Der Induktionsschritt von n nach n+1 ist:

an+1=12an+12↓ Induktionsvoraussetzung: an≥an−1≥12an−1+12=an

Damit ist das monotone Wachstum der Folge bewiesen. Auch die Beschränktheit der Folge nach oben durch 1 kann mit Hilfe vollständiger Induktion gezeigt werden. Hier ist wegen a0=0 der Induktionsanfang a0≤1 direkt gegeben. Im Induktionsschritt haben wir:

an+1=12an+12↓ Induktionsvoraussetzung: an≤1≤121+12=1

Damit ist die Folge (an)n∈ℕ nach oben durch 1 beschränkt. Jetzt können wir auch die Konvergenz zeigen: Weil die Folge monoton steigt und nach oben beschränkt ist, konvergiert die Folge nach dem Monotoniekriterium.

Schritt 2: Grenzwert bestimmen

[Bearbeiten]

Um den Grenzwert der rekursiven Folge zu bestimmen, können wir die gerade bewiesene Konvergenz ausnutzen. Wir wissen so nämlich, dass es ein a∈ℝ mit limn→∞an=a gibt, wobei uns der exakte Wert von a noch unbekannt ist.

Um a zu bestimmen, betrachten wir den Limes limn→∞an+1. Auch dieser Grenzwert ist a und somit erhalten wir

a=limn→∞an+1↓ Rekursionsschritt: an+1=12an+12=limn→∞12an+12↓ Grenzwertsätze=(limn→∞12)⋅(limn→∞an)+limn→∞12=12a+12

Der Wert a muss damit die Gleichung a=12a+12 erfüllen. Aufgrund dieser Bedingung können wir den exakten Wert von a bestimmen:

a=12a+12⟺12a=12⟺a=1

Damit ist a=1 der Grenzwert der Folge (an)n∈ℕ.

Verständnisfrage: Wir haben in der obigen Umformung verwendet, dass limn→∞an+1=a ist. Wieso ist dem so?

limn→∞an+1 ist der Grenzwert der Folge (an+1)n∈ℕ. Diese Folge ist eine Teilfolge von (an)n∈ℕ, bei welcher das erste Folgenglied ausgelassen wurde. Da jede Teilfolge einer konvergenten Folge gegen denselben Grenzwert konvergiert, ist limn→∞an+1=limn→∞an=a.

Übungsaufgaben

[Bearbeiten]

Übungsaufgabe 1

[Bearbeiten]

Aufgabe (Grenzwert einer rekursiv definierten Folge finden)

Gegeben sei eine rekursiv definierte Folge an:

a0=2, an+1=2−1an

Begründe, warum dies Folge konvergiert, und berechne deren Grenzwert über folgende Wege

  1. Durch finden einer expliziten Bildungsvorschrift
  2. Mit Hilfe des Monotoniekriteriums

Lösung (Grenzwert einer rekursiv definierten Folge finden)

Lösung Teilaufgabe 1:

Es gilt

a0=2a1=2−12=32a2=2−132=2−23=43a3=2−143=2−34=54⋮

Daher drängt sich die Vermutung auf, dass an=n+2n+1 für alle n∈ℕ ist. Wir beweisen diese mittels vollständiger Induktion über n:

Aussageform, deren Allgemeingültigkeit für n∈ℕ bewiesen werden soll:

an=n+2n+1

1. Induktionsanfang:

Für n=0 ist a0=0+20+1=2.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

an=n+2n+1

2b. Induktionsbehauptung:

an+1=n+3n+2

2c. Beweis des Induktionsschritts:

an+1=2−1an=IV2−1n+2n+1=2−n+1n+2=2n+4n+2−n+1n+2=n+3n+2

Mit den Rechenregeln für Folgen gilt damit

limn→∞an=limn→∞n+2n+1=limn→∞1+2n1+1n=11=1

Lösung Teilaufgabe 2:

Zunächst beweisen wir, (an)n∈ℕ fallend monoton fallend ist. Das heißt, es ist an+1≤an für alle n∈ℕ. Beweis mittels vollständiger Induktion über n:

Aussageform, deren Allgemeingültigkeit für n∈ℕ bewiesen werden soll:

an+1≤an

1. Induktionsanfang:

a1=2−1a0=2−12=32≤2=a0

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

an+1≤an

2b. Induktionsbehauptung:

an+2≤an+1

2c. Beweis des Induktionsschritts:

an+2=2−1an+1≤IV2−1an=an+1

Außerdem ist (an)n∈ℕ nach unten durch 1 beschränkt, d.h. an≥1 für alle n∈ℕ. Auch dies beweisen wir über vollständige Induktion:

Aussageform, deren Allgemeingültigkeit für n∈ℕ bewiesen werden soll:

an≥1

1. Induktionsanfang:

a0=2≥1

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

an≥1

2b. Induktionsbehauptung:

an+1≥1

2c. Beweis des Induktionsschritts:

an+1=2−1an≥IV2−11=2−1=1

Nach dem Monotoniekriterium ist damit (an)n∈ℕ konvergent. Damit ist limn→∞an=a=limn→∞an+1. Aus der Rekursiuonsgleichung erhalten wir damit

limn→∞an⏟=a=limn→∞2−1an=2−1limn→∞an=2−1a⟺a2=2a−1⟺a2−2a+1⏟=(a−1)2=0⟺a=1

Also konvergiert (an)n∈ℕ gegen a=1.

Übungsaufgabe 2

[Bearbeiten]

Aufgabe (Konvergenz einer rekursiv definierenten Folge berechnen)

Gegeben sei die rekursiv definierte Folge

a0=0a1=2an=13an−1+23an−2
  1. Begründe, warum diese Folge konvergiert, und berechne dessen Grenzwert.
  2. Was passiert bei den Startwerten a0=a1=1?

Lösung (Konvergenz einer rekursiv definierenten Folge berechnen)

Lösung Teilaufgabe 1:

Es gilt

an−an−1=13an−1+23an−2−an−1=23an−2−23an−1=23(an−2−an−1)=−23(an−1−an−2)

Führen wir denselben Schritt n-Mal durch, so erhalten wir

an−an−1=−23(an−1−an−2)=(−23)2(an−2−an−3)=…=(−23)n−1(a1−a0)⏟=2=2⋅(−23)n−1

Mit Hilfe der (Teleskop)-Summe

∑k=1n(ak−ak−1)=an−a0⏟=0=an

folgt nun

an=∑k=1n(ak−ak−1)=2⋅∑k=1n(−23)k−1=2⋅∑k=0n−1(−23)k=2⋅1−(−23)n1−(−23)=2⋅1−(−23)n53=2⋅35(1−(−23)n)=65⋅(1−(−23)n)

Mit limn→∞(−23)n=0 und den Rechenregeln für Folgen gilt

limn→∞an=limn→∞65(1−(−23)n)=65(1−0)=65

Lösung Teilaufgabe 2:

Für a0=1 und a1=1 bekommt man durch Einsetzen:

a2=13⋅1+23⋅1=1

Die Vermutung liegt daher nahe, dass die Folge konstant 1 ist. Mathematisch sauber beweisen wir das durch vollständige Induktion:

Aussageform, deren Allgemeingültigkeit für n∈ℕ bewiesen werden soll:

an=1

1. Induktionsanfang:

Den Induktionsanfang führen wir für n=2. Mit a0=1 und a1=1 folgt a2=1.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

an=1

2b. Induktionsbehauptung:

an+1=1

2c. Beweis des Induktionsschritts:

an+1=13⋅an+23an−1=IV13⋅1+23⋅1=1

Damit gilt auch limn→∞an=limn→∞1=1.

Anwendungsbeispiel: Babylonisches oder Heronisches Wurzelziehen

[Bearbeiten]
Die ersten Folgeglieder der babylonischen Wurzelfolgen zur Berechnung von 2 mit den Startwerten x0=2, x0=4 und x0=8.
Die Folgenglieder der babylonischen Wurzelfolge mit dem Startwert a0=14.

Mit der babylonischen Wurzelfolge möchte ich dir ein Beispiel vorstellen, bei dem die Konvergenz einer rekursiven Folge mit Hilfe des Monotoniekriteriums bewiesen wird. Sie ist eine rekursiv definierte Folge, mit der sich ein Näherungswert für die Quadratwurzel einer Zahl bestimmen lässt und die von Computern zur Quadratwurzelbestimmung benutzt wird. Es gilt nämlich folgender Satz:

Satz (Babylonische Wurzelfunktion)

Sei a eine beliebige reelle Zahl mit a>0. Sei die Folge (xn)n∈ℕ rekursiv definiert durch

x0=axn+1=12(xn+axn)

Dann konvergiert (xn)n∈ℕ gegen a.

Folgenglieder der Folge (xn)n∈ℕ liefern damit (bei ausreichend hohem Index) Näherungswerte für a, wobei der Fehler bei Folgengliedern mit ausreichend hohem Index beliebig klein ist. Wenn man also a mit dem Computer berechnen möchte, dann muss man nur Folgenglieder mit ausreichend großem Index berechnen.

Beweis (Babylonische Wurzelfunktion)

Um zu zeigen, dass die obige Folge wirklich gegen a konvergiert, werden wir in den folgenden zwei Schritten vorgehen:

  1. Wir zeigen zunächst mit dem Monotoniekriterium, dass (xn)n∈ℕ konvergiert.
  2. Wir zeigen mit Hilfe des ersten Schritts, dass der Grenzwert von (xn)n∈ℕ gleich a ist.

Wie du noch sehen wirst, kann der erste Schritt nicht weggelassen werden. Im zweiten Beweisschritt nutzen wir nämlich geschickt das Wissen, dass die Folge (xn)n∈ℕ konvergiert. Eine direkte Berechnung des Grenzwerts mit der Epsilon-Definition ist nur schwer möglich.

Beweisschritt: Die Folge (xn)n∈ℕ konvergiert.

Wir werden die Konvergenz mit Hilfe des Monotoniekriteriums beweisen. Hierzu zeigen wir, dass (xn)n∈ℕ monoton fallend und nach unten beschränkt ist.

Beweisschritt: Die Folge (xn)n∈ℕ ist nach unten beschränkt.

Um die Beschränktheit nach unten zu zeigen, nutzen wir das arithmetisch-geometrische Mittel: Für a,b≥0 gilt nämlich a+b2≥ab. Damit erhalten wir

xn+1=12(xn+axn)=xn+axn2 ↓ a+b2≥ab≥xn⋅axn=a.

Also ist (xn)n∈ℕ nach unten durch a beschränkt.

Beweisschritt: Die Folge (xn)n∈ℕ fällt monoton.

Nun zeigen wir, dass (xn)n∈ℕ monoton fallend ist. Das heißt, dass xn+1≤xn ist. Dazu zeigen wir die äquivalente Aussage xn−xn+1≥0:

xn−xn+1=xn−12(xn+axn)=12(xn−axn)=12xn(xn2−a) ↓ xn≥a⇒xn≥0⇒12xn≥0=12xn⏟≥0(xn2−a) ↓ xn≥a⇒xn2≥a⇒xn2−a≥0=12xn⏟≥0(xn2−a)⏟≥0≥0.

Wir haben gezeigt, dass (xn)n∈ℕ nach unten beschränkt ist und monoton fällt. Also konvergiert diese Folge nach dem Monotoniekriterium.

Beweisschritt: Der Grenzwert von (xn)n∈ℕ ist a.

Zur Berechnung des Grenzwerts wenden wir einen Trick an: Da (xn)n∈ℕ konvergiert, gibt es eine reelle Zahl x mit x=limn→∞xn. Nun ist aber auch limn→∞xn+1=x, da die Folge (xn+1)n∈ℕ eine Teilfolge von (xn)n∈ℕ ist und jede Teilfolge gegen denselben Grenzwert konvergiert. Aus der Rekursionsgleichung und den Grenzwertsätzen ergibt sich:

x=limn→∞xn+1=limn→∞12(xn+axn)↓ Grenzwertsätze=12(limn→∞xn+alimn→∞xn)=12(x+ax)

Diese Gleichung lösen wir nun nach x auf, um den Grenzwert zu erhalten:

x=12(x+ax)⟺x=x2+a2x⟺2x2=x2+a⟺x2=a⟺x=±a

Wegen xn≥0 muss nun aber auch x≥0 gelten. Daher kommt nur die positive Lösung als Grenzwert in Frage. Also ist

limn→∞xn=a

Hinweis

Als Startwert für x0 kann sogar eine beliebige Zahl gewählt werden. Der Beweis kann dann analog geführt werden.

Übungsaufgabe

[Bearbeiten]

Aufgabe (Rekursionsfolge für dritte Wurzel)

Sei x0∈ℝ mit x03>a∈ℝ+. Zeige, dass die für n∈ℕ rekursiv definierte Folge

xn+1=xn−xn3−a3xn2=13⋅(2xn+axn2)

gegen a3 konvergiert. Gehe dabei wie folgt vor:

  1. Zeige mit Hilfe der Bernoullischen Ungleichung: Für jedes x∈ℝ mit x3>a gilt (x−x3−a3x2)3≥a, und beweise damit mittels vollständiger Induktion xn3>a für alle n∈ℕ0
  2. Zeige mit Hilfe von 1: (xn)n∈ℕ0 ist monoton fallend und nach unten beschränkt.
  3. Bestimme den Grenzwert von (xn).

Lösung (Rekursionsfolge für dritte Wurzel)

  1. Erste Ungleichung: Zunächst gilt
    (x−x3−a3x2)3=(x(1−x3−a3x3))3=x3(1−x3−a3x3)3

    Nun ist die Bernoulli-Ungleichung auf den hinteren Faktor anwendbar, denn

    −x3−a3x3>−1⟺−(x3−a)>−3x3⟺−x3+a>−3x3⟺a⏟>0>−2x3⏟<−2a<0

    Also folgt mit der besagten Ungleichung und wegen x3>a>0:

    x3(1−x3−a3x3)3≥x3(1−3⋅x3−a3x3)=x3−(x3−a)=a

    Zweite Ungleichung: Mittels vollständiger Induktion über n:

    Induktionsanfang: n=0. x03≥a nach Voraussetzung.

    Induktionsschritt: n→n+1. xn+13=(xn−xn3−a3xn2)3≥a nach der ersten Ungleichung, da nach der Induktionsvoraussetzung xn3>a gilt.

  2. (xn) ist monoton fallend: Sei n∈ℕ. Wir wissen aus 1., dass xn3−a>0. Daraus folgt auch, dass xn≠0 und damit 3xn2>0. Folglich gilt
     xn+1−xn= xn−xn3−a3xn2−xn↓ rekrusive Definition von xn+1= −xn3−a3xn2↓ xn3−a>0 und 3xn2>0< 0.

    Also gilt xn+1<xn.

    (xn) ist nach unten beschränkt: Wegen xn3≥a folgt sofort

    xn≥a3
  3. Da (xn) nach 2. monoton fallend und nach unten beschränkt ist, folgt mit dem Monotoniekriterium die Konvergenz der Folge. Setzen wir limn→∞xn=limn→∞xn+1=x, so gilt mit der rekursiven Definition der Folge (xn):
    x−x3−a3x2=x⟺x3−a3x2=0⟺x3−a=0⟺x3=a⟺x=a3

Hinweis

Analog lässt sich allgemein für jede natürliche Zahl k≥2 und für reelle Zahlen x0>0 und a>0 zeigen, dass die rekursiv definierte Folge (xn)n∈ℕ mit

xn+1=1k((k−1)xn−axnk−1)

gegen ak konvergiert.