Konvergenz rekursiver Folgen beweisen – Serlo „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 eine durch und durch 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 rekursiv definiert ist, können wir ihren Grenzwert nicht direkt ablesen. Auch sind im Allgemeinen Abschätzungen für den Term mit einer reellen Zahl schwierig, weil wir keine explizite Form des Folgenglieds 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 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:

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

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

Anhand dieser Beispiele liegt die Vermutung nahe, dass wir wählen können. Es sollte also gelten:

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

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

Damit haben wir gezeigt. Nun können wir das Konvergenzverhalten mit den Mitteln untersuchen, die wir bereits kennengelernt haben. Beispielsweise haben wir bereits bewiesen und damit können wir die Grenzwertsätze anwenden, um die Konvergenz der Folge zu beweisen:

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

Betrachten wir die Differenz zweier aufeinanderfolgender Glieder und , so erhalten wir

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

In jedem Schritt kommt also als Vorfaktor hinzu. Nach insgesamt Schritten erhalten wir

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

Auf der rechten Seite ergibt sich die geometrische Summe

Damit erhalten wir die explizite Darstellung

Mit und den Rechenregeln für Folgen gilt

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:

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

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

Der Induktionsschritt von nach ist:

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

Damit ist die Folge nach oben durch 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 mit gibt, wobei uns der exakte Wert von noch unbekannt ist.

Um zu bestimmen, betrachten wir den Limes . Auch dieser Grenzwert ist und somit erhalten wir

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

Damit ist der Grenzwert der Folge .

Verständnisfrage: Wir haben in der obigen Umformung verwendet, dass ist. Wieso ist dem so?

ist der Grenzwert der Folge . Diese Folge ist eine Teilfolge von , bei welcher das erste Folgenglied ausgelassen wurde. Da jede Teilfolge einer konvergenten Folge gegen denselben Grenzwert konvergiert, ist .

Übungsaufgaben[Bearbeiten]

Übungsaufgabe 1[Bearbeiten]

Aufgabe (Grenzwert einer rekursiv definierten Folge finden)

Gegeben sei eine rekursiv definierte Folge :

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

Daher drängt sich die Vermutung auf, dass für alle ist. Wir beweisen diese mittels vollständiger Induktion über :

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

1. Induktionsanfang:

Für ist .

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

2b. Induktionsbehauptung:

2c. Beweis des Induktionsschritts:

Mit den Rechenregeln für Folgen gilt damit

Lösung Teilaufgabe 2:

Zunächst beweisen wir, fallend monoton fallend ist. Das heißt, es ist für alle . Beweis mittels vollständiger Induktion über :

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

1. Induktionsanfang:

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

2b. Induktionsbehauptung:

2c. Beweis des Induktionsschritts:

Außerdem ist nach unten durch beschränkt, d.h. für alle . Auch dies beweisen wir über vollständige Induktion:

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

1. Induktionsanfang:

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

2b. Induktionsbehauptung:

2c. Beweis des Induktionsschritts:

Nach dem Monotoniekriterium ist damit konvergent. Damit ist . Aus der Rekursiuonsgleichung erhalten wir damit

Also konvergiert gegen .

Übungsaufgabe 2[Bearbeiten]

Aufgabe (Konvergenz einer rekursiv definierenten Folge berechnen)

Gegeben sei die rekursiv definierte Folge

  1. Begründe, warum diese Folge konvergiert, und berechne dessen Grenzwert.
  2. Was passiert bei den Startwerten ?

Lösung (Konvergenz einer rekursiv definierenten Folge berechnen)

Lösung Teilaufgabe 1:

Es gilt

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

Mit Hilfe der (Teleskop)-Summe

folgt nun

Mit und den Rechenregeln für Folgen gilt

Lösung Teilaufgabe 2:

Für und bekommt man durch Einsetzen:

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

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

1. Induktionsanfang:

Den Induktionsanfang führen wir für . Mit und folgt .

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

2b. Induktionsbehauptung:

2c. Beweis des Induktionsschritts:

Damit gilt auch .

Anwendungsbeispiel: Babylonisches oder Heronisches Wurzelziehen[Bearbeiten]

Die ersten Folgeglieder der babylonischen Wurzelfolgen zur Berechnung von mit den Startwerten , und .
Die Folgenglieder der babylonischen Wurzelfolge mit dem Startwert .

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 eine beliebige reelle Zahl mit . Sei die Folge rekursiv definiert durch

Dann konvergiert gegen .

Folgenglieder der Folge liefern damit (bei ausreichend hohem Index) Näherungswerte für , wobei der Fehler bei Folgengliedern mit ausreichend hohem Index beliebig klein ist. Wenn man also 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 konvergiert, werden wir in den folgenden zwei Schritten vorgehen:

  1. Wir zeigen zunächst mit dem Monotoniekriterium, dass konvergiert.
  2. Wir zeigen mit Hilfe des ersten Schritts, dass der Grenzwert von gleich 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 konvergiert. Eine direkte Berechnung des Grenzwerts mit der Epsilon-Definition ist nur schwer möglich.

Beweisschritt: Die Folge konvergiert.

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

Beweisschritt: Die Folge ist nach unten beschränkt.

Um die Beschränktheit nach unten zu zeigen, nutzen wir das arithmetisch-geometrische Mittel: Für gilt nämlich . Damit erhalten wir

Also ist nach unten durch beschränkt.

Beweisschritt: Die Folge fällt monoton.

Nun zeigen wir, dass monoton fallend ist. Das heißt, dass ist. Dazu zeigen wir die äquivalente Aussage :

Wir haben gezeigt, dass nach unten beschränkt ist und monoton fällt. Also konvergiert diese Folge nach dem Monotoniekriterium.

Beweisschritt: Der Grenzwert von ist .

Zur Berechnung des Grenzwerts wenden wir einen Trick an: Da konvergiert, gibt es eine reelle Zahl mit . Nun ist aber auch , da die Folge eine Teilfolge von ist und jede Teilfolge gegen denselben Grenzwert konvergiert. Aus der Rekursionsgleichung und den Grenzwertsätzen ergibt sich:

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

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

Hinweis

Als Startwert für 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 mit . Zeige, dass die für rekursiv definierte Folge

gegen konvergiert. Gehe dabei wie folgt vor:

  1. Zeige mit Hilfe der Bernoullischen Ungleichung: Für jedes mit gilt , und beweise damit mittels vollständiger Induktion für alle
  2. Zeige mit Hilfe von 1: ist monoton fallend und nach unten beschränkt.
  3. Bestimme den Grenzwert von .

Lösung (Rekursionsfolge für dritte Wurzel)

  1. Erste Ungleichung: Zunächst gilt

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

    Also folgt mit der besagten Ungleichung und wegen :

    Zweite Ungleichung: Mittels vollständiger Induktion über :

    Induktionsanfang: . nach Voraussetzung.

    Induktionsschritt: . nach der ersten Ungleichung, da nach der Induktionsvoraussetzung gilt.

  2. ist monoton fallend: Sei . Wir wissen aus 1., dass . Daraus folgt auch, dass und damit . Folglich gilt

    Also gilt .

    ist nach unten beschränkt: Wegen folgt sofort

  3. Da nach 2. monoton fallend und nach unten beschränkt ist, folgt mit dem Monotoniekriterium die Konvergenz der Folge. Setzen wir , so gilt mit der rekursiven Definition der Folge :

Hinweis

Analog lässt sich allgemein für jede natürliche Zahl und für reelle Zahlen und zeigen, dass die rekursiv definierte Folge mit

gegen konvergiert.