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

Nehme folgende Aufgabe:
Sei (a_{n})_{{n\in \mathbb{N} }} eine durch a_{0}=0 und durch a_{{n+1}}={\tfrac 12}a_{n}+{\tfrac 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 (a_{n})_{{n\in \mathbb{N} }} rekursiv definiert ist, können wir ihren Grenzwert nicht direkt ablesen. Auch sind im Allgemeinen Abschätzungen für den Term |a-a_{n}| mit einer reellen Zahl schwierig, weil wir keine explizite Form des Folgenglieds a_{n} kennen.

Lösungsstrategien

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

Eine mögliche Lösungsstrategie ist die, eine explizite Bildungsvorschrift von (a_{n})_{{n\in \mathbb{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:
{\begin{aligned}a_{0}&=0\\[0.3em]a_{1}&={\frac 12}a_{0}+{\frac 12}={\frac 12}\cdot 0+{\frac 12}={\frac 12}\\[0.3em]a_{2}&={\frac 12}a_{1}+{\frac 12}={\frac 12}\cdot {\frac 12}+{\frac 12}={\frac 34}\\[0.3em]a_{3}&={\frac 12}a_{2}+{\frac 12}={\frac 12}\cdot {\frac 34}+{\frac 12}={\frac 78}\\[0.3em]a_{4}&={\frac 12}a_{3}+{\frac 12}={\frac 12}\cdot {\frac 78}+{\frac 12}={\frac {15}{16}}\\[0.3em]&\vdots \end{aligned}}
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\mapsto a_{n} finden. Wir suchen also einen Term f(x) für den gilt:
{\begin{aligned}f(0)&=0\\[0.3em]f(1)&={\frac 12}\\[0.3em]f(2)&={\frac 34}\\[0.3em]f(3)&={\frac 78}\\[0.3em]&\vdots \end{aligned}}
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
{\begin{aligned}{\begin{array}{rll}f(0)&=0&={\frac {2^{0}-1}{2^{0}}}\\[0.3em]f(1)&={\frac 12}&={\frac {2^{1}-1}{2^{1}}}\\[0.3em]f(2)&={\frac 34}&={\frac {2^{2}-1}{2^{2}}}\\[0.3em]f(3)&={\frac 78}&={\frac {2^{3}-1}{2^{3}}}\\[0.3em]&\vdots \end{array}}\end{aligned}}
Anhand dieser Beispiele liegt die Vermutung nahe, dass f(n)={\frac {2^{n}-1}{2^{n}}} wählen können. Es sollte also gelten
a_{n}=f(n)={\frac {2^{n}-1}{2^{n}}}=1-{\frac {1}{2^{n}}}=1-\left({\frac 1{2}}\right)^{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:
a_{0}=0=1-1=1-\left({\frac 12}\right)^{0}
Den Induktionsschritt von n nach n+1 können wir nach Anwendung des Rekursionsschritts führen:
{\begin{aligned}a_{{n+1}}&={\frac 12}{\color {Teal}a_{n}}+{\frac 12}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung}}\right.}\\[0.3em]&={\frac 12}\cdot {\color {Teal}\left(1-\left({\frac 12}\right)^{n}\right)}+{\frac 12}\\[0.3em]&={\frac 12}-\left({\frac 12}\right)^{{n+1}}+{\frac 12}\\[0.3em]&=1-\left({\frac 12}\right)^{{n+1}}\end{aligned}}
Damit haben wir a_{n}=1-\left({\frac 12}\right)^{n} gezeigt. Nun können wir das Konvergenzverhalten mit den Mitteln untersuchen, die wir bereits kennengelernt haben. Beispielsweise haben wir bereits \lim _{{n\to \infty }}\left({\frac 12}\right)^{n}=0 bewiesen und damit können wir die Grenzwertsätze anwenden, um die Konvergenz der Folge zu beweisen:
{\begin{aligned}\lim _{{n\to \infty }}a_{n}&=\lim _{{n\to \infty }}1-\left({\frac 12}\right)^{n}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Grenzwertsatz: }}\lim _{{n\to \infty }}(a_{n}+b_{n})=\lim _{{n\to \infty }}a_{n}+\lim _{{n\to \infty }}b_{n}\right.}\\[0.3em]&=\lim _{{n\to \infty }}1-\lim _{{n\to \infty }}\left({\frac 12}\right)^{n}\\[0.3em]&=1-0=1\end{aligned}}

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

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
a_{0}=0,\ a_{1}=1,\ a_{{n}}={\frac 12}a_{{n-1}}+{\frac 12}a_{{n-2}}
Betrachten wir die Differenz zweier aufeinanderfolgender Glieder a_{n} und a_{{n-1}}, so erhalten wir
{\begin{aligned}a_{{n}}-a_{{n-1}}&={\frac 12}a_{{n-1}}+{\frac 12}a_{{n-2}}-a_{{n-1}}\\&={\frac 12}a_{{n-2}}-{\frac 12}a_{{n-1}}\\&={\frac 12}(a_{{n-2}}-a_{{n-1}})\\&=-{\frac 12}(a_{{n-1}}-a_{{n-2}})\end{aligned}}
Führen wir denselben Schritt erneut durch, so erhalten wir
{\begin{aligned}a_{{n}}-a_{{n-1}}&=-{\frac 12}(a_{{n-1}}-a_{{n-2}})\\&=-{\frac 12}\left({\frac 12}a_{{n-2}}+{\frac 12}a_{{n-3}}-a_{{n-2}}\right)\\&=-{\frac 12}\left({\frac 12}a_{{n-3}}-{\frac 12}a_{{n-2}}\right)\\&=\left(-{\frac 12}\right)^{2}(a_{{n-2}}-a_{{n-3}})\end{aligned}}
In jedem Schritt kommt also -{\tfrac 12} als Vorfaktor hinzu. Nach insgesamt n-1 Schritten erhalten wir
a_{n}-a_{{n-1}}=\left(-{\frac 12}\right)^{{n-1}}\underbrace {(a_{1}-a_{0})}_{{=1}}=\left(-{\frac 12}\right)^{{n-1}}
Damit können wir nun noch nicht den Grenzwert berechnen, da wir „nur“ eine Bildungsvorschrift für a_{n}-a_{{n-1}} und noch nicht für a_{n} haben. Diese erreichen wir, wenn wir die (Teleskop-)Summe über a_{k}-a_{{k-1}} bilden:
\sum _{{k=1}}^{n}(a_{k}-a_{{k-1}})=a_{n}-a_{0}=a_{n}
Auf der rechten Seite ergibt sich die geometrische Summe
\sum _{{k=1}}^{n}\left(-{\frac 12}\right)^{{k-1}}=\sum _{{k=0}}^{{n-1}}\left(-{\frac 12}\right)^{{k}}={\frac {1-(-{\frac 12})^{n}}{1-(-{\frac 12})}}={\frac {1-(-{\frac 12})^{n}}{{\frac 32}}}={\tfrac 23}(1-(-{\tfrac 12})^{n})
Damit erhalten wir die explizite Darstellung
a_{n}={\tfrac 23}(1-(-{\tfrac 12})^{n})
Mit \lim _{{n\to \infty }}(-{\tfrac 12})^{n}=0 und den Rechenregeln für Folgen gilt
\lim _{{n\to \infty }}a_{n}=\lim _{{n\to \infty }}{\tfrac 23}(1-(-{\tfrac 12})^{n})={\tfrac 23}(1-0)={\tfrac 23}

Lösungsweg: Monotoniekriterium anwenden

Schritt 1: Beweis der Konvergenz

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:
{\begin{aligned}a_{0}&=0\\[0.3em]a_{1}&={\frac 12}a_{0}+{\frac 12}={\frac 12}\cdot 0+{\frac 12}={\frac 12}\\[0.3em]a_{2}&={\frac 12}a_{1}+{\frac 12}={\frac 12}\cdot {\frac 12}+{\frac 12}={\frac 34}\\[0.3em]a_{3}&={\frac 12}a_{2}+{\frac 12}={\frac 12}\cdot {\frac 34}+{\frac 12}={\frac 78}\\[0.3em]a_{4}&={\frac 12}a_{3}+{\frac 12}={\frac 12}\cdot {\frac 78}+{\frac 12}={\frac {15}{16}}\\[0.3em]&\vdots \end{aligned}}
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 a_{1}\geq a_{0} ist:
a_{1}={\frac 12}a_{0}+{\frac 12}={\frac 12}\cdot 0+{\frac 12}={\frac 12}\geq 0=a_{0}
Der Induktionsschritt von n nach n+1 ist:
{\begin{aligned}a_{{n+1}}&={\frac 12}{\color {Teal}a_{n}}+{\frac 12}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung: }}a_{n}\geq a_{{n-1}}\right.}\\[0.3em]&\geq {\frac 12}{\color {Teal}a_{{n-1}}}+{\frac 12}=a_{n}\end{aligned}}
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 a_{0}=0 der Induktionsanfang a_{0}\leq 1 direkt gegeben. Im Induktionsschritt haben wir:
{\begin{aligned}a_{{n+1}}&={\frac 12}{\color {Teal}a_{n}}+{\frac 12}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung: }}a_{n}\leq 1\right.}\\[0.3em]&\leq {\frac 12}{\color {Teal}1}+{\frac 12}=1\end{aligned}}
Damit ist die Folge (a_{n})_{{n\in \mathbb{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

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\in \mathbb{R} mit \lim _{{n\to \infty }}a_{n}=a gibt, wobei uns der exakte Wert von a noch unbekannt ist.
Um a zu bestimmen, betrachten wir den Limes \lim _{{n\to \infty }}a_{{n+1}}. Auch dieser Grenzwert ist a und somit erhalten wir
{\begin{aligned}a&=\lim _{{n\to \infty }}a_{{n+1}}\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{Rekursionsschritt: }}a_{{n+1}}={\frac 12}a_{n}+{\frac 12}\right.}\\[0.5em]&=\lim _{{n\to \infty }}{\frac 12}a_{n}+{\frac 12}\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{Grenzwertsätze}}\right.}\\[0.5em]&=\left(\lim _{{n\to \infty }}{\frac 12}\right)\cdot \left(\lim _{{n\to \infty }}a_{n}\right)+\lim _{{n\to \infty }}{\frac 12}\\[0.5em]&={\frac 12}a+{\frac 12}\end{aligned}}
Der Wert a muss damit die Gleichung a={\tfrac 12}a+{\tfrac 12} erfüllen. Aufgrund dieser Bedingung können wir den exakten Wert von a bestimmen:
a={\frac 12}a+{\frac 12}\iff {\frac 12}a={\frac 12}\iff a=1
Damit ist a=1 der Grenzwert der Folge (a_{n})_{{n\in \mathbb{N} }}.
Verständnisfrage: Wir haben in der obigen Umformung verwendet, dass \lim _{{n\to \infty }}a_{{n+1}}=a ist. Wieso ist dem so?
\lim _{{n\to \infty }}a_{{n+1}} ist der Grenzwert der Folge (a_{{n+1}})_{{n\in \mathbb{N} }}. Diese Folge ist eine Teilfolge von (a_{{n}})_{{n\in \mathbb{N} }}, bei welcher das erste Folgenglied ausgelassen wurde. Da jede Teilfolge einer konvergenten Folge gegen denselben Grenzwert konvergiert, ist \lim _{{n\to \infty }}a_{{n+1}}=\lim _{{n\to \infty }}a_{n}=a.

Übungsaufgaben

Übungsaufgabe 1

Grenzwert einer rekursiv definierenten Folge finden
Gegeben sei eine rekursiv definierte Folge a_{n}:
a_{0}=2,\ a_{{n+1}}=2-{\frac {1}{a_{n}}}
Begründe, warum dies Folge konvergiert, und berechne deren Grenzwert über folgende Wege
Übung 1:
Durch finden einer expliziten Bildungsvorschrift
Übung 2:
Mit Hilfe des Monotoniekriteriums
Lösung: Lösung von Teilaufgabe 1:
Es gilt
{\begin{aligned}a_{0}&=2\\[0.3em]a_{1}&=2-{\frac 12}={\frac 32}\\[0.3em]a_{2}&=2-{\frac {1}{{\frac 32}}}=2-{\frac 23}={\frac 43}\\[0.3em]a_{3}&=2-{\frac {1}{{\frac 43}}}=2-{\frac 34}={\frac 54}\\[0.3em]&\vdots \end{aligned}}
Daher drängt sich die Vermutung auf, dass a_{n}={\frac {n+2}{n+1}} für alle n\in \mathbb{N} ist. Wir beweisen diese mittels vollständiger Induktion über n:
Aussage, die wir für alle n\in \mathbb{N} beweisen wollen:
a_{n}={\frac {n+2}{n+1}}
  1. Induktionsanfang:Für n=0 ist a_{0}={\tfrac {0+2}{0+1}}=2.
  2. Induktionsschritt:
    1. Induktionsvoraussetzung:
      a_{n}={\frac {n+2}{n+1}}
    2. Induktionsbehauptung:
      a_{{n+1}}={\frac {n+3}{n+2}}
    3. Beweis des Induktionsschritts:
      {\begin{aligned}a_{{n+1}}&=2-{\frac 1{a_{n}}}{\overset {{\text{IV}}}{=}}2-{\tfrac {1}{{\frac {n+2}{n+1}}}}\\[0.5em]&=2-{\frac {n+1}{n+2}}={\frac {2n+4}{n+2}}-{\frac {n+1}{n+2}}={\frac {n+3}{n+2}}\end{aligned}}
Mit den Rechenregeln für Folgen gilt damit
\lim _{{n\to \infty }}a_{n}=\lim _{{n\to \infty }}{\frac {n+2}{n+1}}=\lim _{{n\to \infty }}{\frac {1+{\frac 2n}}{1+{\frac 1n}}}={\frac 11}=1
Lösung von Teilaufgabe 2:
Zunächst beweisen wir, (a_{n})_{{n\in \mathbb{N} }} fallend monoton fallend ist. Das heißt, es ist a_{{n+1}}\leq a_{n} für alle n\in \mathbb{N} . Beweis mittels vollständiger Induktion über n:
Aussage, die wir für alle n\in \mathbb{N} beweisen wollen:
a_{{n+1}}\leq a_{n}
  1. Induktionsanfang:
    a_{1}=2-{\frac 1{a_{0}}}=2-{\frac 12}={\frac {3}{2}}\leq 2=a_{0}
  2. Induktionsschritt:
    1. Induktionsvoraussetzung:
      a_{{n+1}}\leq a_{n}
    2. Induktionsbehauptung:
      a_{{n+2}}\leq a_{{n+1}}
    3. Beweis des Induktionsschritts:
      a_{{n+2}}=2-{\frac 1{a_{{n+1}}}}{\overset {{\text{IV}}}{\leq }}2-{\frac {1}{a_{n}}}=a_{{n+1}}
Außerdem ist (a_{n})_{{n\in \mathbb{N} }} nach unten durch 1 beschränkt, d.h. a_{{n}}\geq 1 für alle n\in \mathbb{N} . Auch dies beweisen wir über vollständige Induktion:
Aussage, die wir für alle n\in \mathbb{N} beweisen wollen:
a_{n}\geq 1
  1. Induktionsanfang:
    a_{0}=2\geq 1
  2. Induktionsschritt:
    1. Induktionsvoraussetzung:
      a_{n}\geq 1
    2. Induktionsbehauptung:
      a_{{n+1}}\geq 1
    3. Beweis des Induktionsschritts:
      a_{{n+1}}=2-{\frac 1{a_{{n}}}}{\overset {{\text{IV}}}{\geq }}2-{\frac {1}{1}}=2-1=1
Nach dem Monotoniekriterium ist damit (a_{n})_{{n\in \mathbb{N} }} konvergent. Damit ist \lim _{{n\to \infty }}a_{n}=a=\lim _{{n\to \infty }}a_{{n+1}}. Aus der Rekursiuonsgleichung erhalten wir damit
{\begin{aligned}&\underbrace {\lim _{{n\to \infty }}a_{n}}_{{=a}}=\lim _{{n\to \infty }}2-{\frac 1{a_{n}}}=2-{\frac 1{\lim _{{n\to \infty }}a_{n}}}=2-{\frac 1a}\\[0.3em]\iff &a^{2}=2a-1\\[0.3em]\iff &\underbrace {a^{2}-2a+1}_{{=(a-1)^{2}}}=0\\[0.3em]\iff &a=1\end{aligned}}
Also konvergiert (a_{n})_{{n\in \mathbb{N} }} gegen a=1.

Übungsaufgabe 2

Konvergenz einer rekursiv definierenten Folge berechnen
Gegeben sei die rekursiv definierte Folge
{\begin{aligned}a_{0}&=0\\a_{1}&=2\\a_{{n}}&={\frac 13}a_{{n-1}}+{\frac 23}a_{{n-2}}\end{aligned}}
Übung 1:
Begründe, warum diese Folge konvergiert, und berechne dessen Grenzwert.
Übung 2:
Was passiert bei den Startwerten a_{0}=a_{1}=1?
Lösung: Lösung von Teilaufgabe 1:
Es gilt
{\begin{aligned}a_{{n}}-a_{{n-1}}&={\frac 13}a_{{n-1}}+{\frac 23}a_{{n-2}}-a_{{n-1}}\\&={\frac 23}a_{{n-2}}-{\frac 23}a_{{n-1}}\\&={\frac 23}(a_{{n-2}}-a_{{n-1}})\\&=-{\frac 23}(a_{{n-1}}-a_{{n-2}})\end{aligned}}
Führen wir denselben Schritt n-Mal durch, so erhalten wir
{\begin{aligned}a_{{n}}-a_{{n-1}}&=-{\frac 23}(a_{{n-1}}-a_{{n-2}})\\&=\left(-{\frac 23}\right)^{2}(a_{{n-2}}-a_{{n-3}})\\&=\ldots \\&=\left(-{\frac 23}\right)^{{n-1}}\underbrace {(a_{1}-a_{0})}_{{=2}}\\&=2\cdot \left(-{\frac 23}\right)^{{n-1}}\end{aligned}}
Mit Hilfe der (Teleskop)-Summe
\sum _{{k=1}}^{n}(a_{k}-a_{{k-1}})=a_{n}-\underbrace {a_{0}}_{{=0}}=a_{n}
folgt nun
{\begin{aligned}a_{n}&=\sum _{{k=1}}^{n}(a_{k}-a_{{k-1}})\\&=2\cdot \sum _{{k=1}}^{n}\left(-{\frac 23}\right)^{{k-1}}\\&=2\cdot \sum _{{k=0}}^{{n-1}}\left(-{\frac 23}\right)^{{k}}\\&=2\cdot {\frac {1-(-{\frac 23})^{n}}{1-(-{\frac 23})}}\\&=2\cdot {\frac {1-(-{\frac 23})^{n}}{{\frac 53}}}\\&=2\cdot {\tfrac 35}(1-(-{\tfrac 23})^{n})\\&={\tfrac 65}\cdot (1-(-{\tfrac 23})^{n})\end{aligned}}
Mit \lim _{{n\to \infty }}(-{\tfrac 23})^{n}=0 und den Rechenregeln für Folgen gilt
\lim _{{n\to \infty }}a_{n}=\lim _{{n\to \infty }}{\frac 65}(1-(-{\frac 23})^{n})={\frac 65}(1-0)={\frac 65}
Lösung von Teilaufgabe 2:
Für a_{0}=1 und a_{1}=1 bekommt man durch Einsetzen:
a_{2}={\frac 13}\cdot 1+{\frac 23}\cdot 1=1
Die Vermutung liegt daher nahe, dass die Folge konstant 1 ist. Mathematisch sauber beweisen wir das durch vollständige Induktion:
Aussage, die wir für alle n\in \mathbb{N} beweisen wollen:
a_{n}=1
  1. Induktionsanfang:Den Induktionsanfang führen wir für n=2. Mit a_{0}=1 und a_{1}=1 folgt a_{{2}}=1.
  2. Induktionsschritt:
    1. Induktionsvoraussetzung:
      a_{n}=1
    2. Induktionsbehauptung:
      a_{{n+1}}=1
    3. Beweis des Induktionsschritts:
      a_{{n+1}}={\frac 13}\cdot a_{n}+{\frac 23}a_{{n-1}}{\overset {{\text{IV}}}{=}}{\frac 13}\cdot 1+{\frac 23}\cdot 1=1
Damit gilt auch \lim _{{n\to \infty }}a_{n}=\lim _{{n\to \infty }}1=1.

Anwendungsbeispiel: Babylonisches oder Heronisches Wurzelziehen

error: non-centered image not implemented, yet! error: non-centered image not implemented, yet!
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 (x_{n})_{{n\in \mathbb{N} }} rekursiv definiert durch
{\begin{aligned}x_{0}&=a\\x_{{n+1}}&={\frac 12}\left(x_{n}+{\frac {a}{x_{n}}}\right)\end{aligned}}
Dann konvergiert (x_{n})_{{n\in \mathbb{N} }} gegen {\sqrt {a}}.
ErklärungFolgenglieder der Folge (x_{n})_{{n\in \mathbb{N} }} liefern damit (bei ausreichend hohem Index) Näherungswerte für {\sqrt {a}}, wobei der Fehler bei Folgengliedern mit ausreichend hohem Index beliebig klein ist. Wenn man also {\sqrt a} mit dem Computer berechnen möchte, dann muss man nur Folgenglieder mit ausreichend großem Index berechnen.
Beweis
Um zu zeigen, dass die obige Folge wirklich gegen {\sqrt {a}} konvergiert, werden wir in den folgenden zwei Schritten vorgehen:
  1. Wir zeigen zunächst mit dem Monotoniekriterium, dass (x_{n})_{{n\in \mathbb{N} }} konvergiert.
  2. Wir zeigen mit Hilfe des ersten Schritts, dass der Grenzwert von (x_{n})_{{n\in \mathbb{N} }} gleich {\sqrt {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 (x_{n})_{{n\in \mathbb{N} }} konvergiert. Eine direkte Berechnung des Grenzwerts mit der Epsilon-Definition ist nur schwer möglich.
Beweisschritt: Die Folge (x_{n})_{{n\in \mathbb{N} }} konvergiert.
Wir werden die Konvergenz mit Hilfe des Monotoniekriteriums beweisen. Hierzu zeigen wir, dass (x_{n})_{{n\in \mathbb{N} }} monoton fallend und nach unten beschränkt ist.
Beweisschritt: Die Folge (x_{n})_{{n\in \mathbb{N} }} ist nach unten beschränkt.
Um die Beschränktheit nach unten zu zeigen, nutzen wir das arithmetisch-geometrische Mittel: Für a,b\geq 0 gilt nämlich {\tfrac {a+b}{2}}\geq {\sqrt {ab}}. Damit erhalten wir
{\begin{aligned}x_{{n+1}}&={\frac 12}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac {x_{n}+{\frac {a}{x_{n}}}}{2}}\\[0.5em]&\ {\color {OliveGreen}\left\downarrow \ {\frac {a+b}{2}}\geq {\sqrt {ab}}\right.}\\[0.5em]&\geq {\sqrt {x_{n}\cdot {\frac {a}{x_{n}}}}}\\[0.5em]&={\sqrt {a}}.\end{aligned}}
Also ist (x_{n})_{{n\in \mathbb{N} }} nach unten durch {\sqrt {a}} beschränkt.
Beweisschritt: Die Folge (x_{n})_{{n\in \mathbb{N} }} fällt monoton.
Nun zeigen wir, dass (x_{n})_{{n\in \mathbb{N} }} monoton fallend ist. Das heißt, dass x_{{n+1}}\leq x_{n} ist. Dazu zeigen wir die äquivalente Aussage x_{n}-x_{{n+1}}\geq 0:
{\begin{aligned}x_{{n}}-x_{{n+1}}&=x_{n}-{\frac 12}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac 12}\left(x_{n}-{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac {1}{2x_{n}}}(x_{n}^{2}-a)\\[0.5em]&\ {\color {OliveGreen}\left\downarrow \ x_{n}\geq {\sqrt {a}}\Rightarrow x_{n}\geq 0\Rightarrow {\frac {1}{2x_{n}}}\geq 0\right.}\\[0.5em]&=\underbrace {{\frac {1}{2x_{n}}}}_{{\geq 0}}(x_{n}^{2}-a)\\[0.5em]&\ {\color {OliveGreen}\left\downarrow \ x_{n}\geq {\sqrt {a}}\Rightarrow x_{n}^{2}\geq a\Rightarrow x_{n}^{2}-a\geq 0\right.}\\[0.5em]&=\underbrace {{\frac {1}{2x_{n}}}}_{{\geq 0}}\underbrace {(x_{n}^{2}-a)}_{{\geq 0}}\\&\geq 0.\end{aligned}}
Wir haben gezeigt, dass (x_{n})_{{n\in \mathbb{N} }} nach unten beschränkt ist und monoton fällt. Also konvergiert diese Folge nach dem Monotoniekriterium.
Beweisschritt: Der Grenzwert von (x_{n})_{{n\in \mathbb{N} }} ist {\sqrt {a}}.
Zur Berechnung des Grenzwerts wenden wir einen Trick an: Da (x_{n})_{{n\in \mathbb{N} }} konvergiert, gibt es eine reelle Zahl x mit x=\lim _{{n\to \infty }}x_{n}. Nun ist aber auch \lim _{{n\to \infty }}x_{{n+1}}=x, da die Folge (x_{{n+1}})_{{n\in \mathbb{N} }} eine Teilfolge von (x_{n})_{{n\in \mathbb{N} }} ist und jede Teilfolge gegen denselben Grenzwert konvergiert. Aus der Rekursionsgleichung und den Grenzwertsätzen ergibt sich:
{\begin{aligned}x&=\lim _{{n\to \infty }}x_{{n+1}}\\[0.3em]&=\lim _{{n\to \infty }}{\frac 12}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Grenzwertsätze}}\right.}\\[0.3em]&={\frac 12}\left(\lim _{{n\to \infty }}x_{n}+{\frac {a}{\lim _{{n\to \infty }}x_{n}}}\right)\\[0.3em]&={\frac 12}\left(x+{\frac {a}{x}}\right)\end{aligned}}
Diese Gleichung lösen wir nun nach x auf, um den Grenzwert zu erhalten:
{\begin{aligned}x={\frac 12}\left(x+{\frac {a}{x}}\right)&\iff x={\frac {x^{2}+a}{2x}}\\[0.5em]&\iff 2x^{2}=x^{2}+a\\[0.5em]&\iff x^{2}=a\\[0.5em]&\iff x=\pm {\sqrt {a}}\end{aligned}}
Wegen x_{n}\geq 0 muss nun aber auch x\geq 0 gelten. Daher kommt nur die positive Lösung als Grenzwert in Frage. Also ist
\lim _{{n\to \infty }}x_{n}={\sqrt {a}}
Hinweis:
Als Startwert für x_{0} kann sogar eine beliebige Zahl gewählt werden. Der Beweis kann dann analog geführt werden.

Übungsaufgabe

Übung: Rekursionsfolge für dritte Wurzel
Sei x_{0}\in \mathbb{R} mit x_{0}^{3}>a\in \mathbb{R} ^{+}. Zeige, dass die für n\in \mathbb{N} rekursiv definierte Folge
x_{{n+1}}=x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}={\frac 13}\cdot \left(2x_{n}+{\frac {a}{x_{n}^{2}}}\right)
gegen {\sqrt[ {3}]{a}} konvergiert. Gehe dabei wie folgt vor:
  1. Zeige mit Hilfe der error: internal links not implemented, yet! : Für jedes x\in \mathbb{R} mit x^{3}>a gilt \left(x-{\frac {x^{3}-a}{3x^{2}}}\right)^{3}\geq a, und beweise damit mittels vollständiger Induktion x_{n}^{3}>a für alle n\in \mathbb{N} _{0}
  2. Zeige mit Hilfe von 1: (x_{n})_{{n\in \mathbb{N} _{0}}} ist monoton fallend und nach unten beschränkt.
  3. Bestimme den Grenzwert von (x_{n}).
  1. Erste Ungleichung: Zunächst gilt
    \left(x-{\frac {x^{3}-a}{3x^{2}}}\right)^{3}=\left(x\left(1-{\frac {x^{3}-a}{3x^{3}}}\right)\right)^{3}=x^{3}\left(1-{\frac {x^{3}-a}{3x^{3}}}\right)^{3}
    Nun ist die Bernoulli-Ungleichung auf den hinteren Faktor anwendbar, denn
    -{\frac {x^{3}-a}{3x^{3}}}>-1\iff -(x^{3}-a)>-3x^{3}\iff -x^{3}+a>-3x^{3}\iff \underbrace {a}_{{>0}}>\underbrace {-2x^{3}}_{{<-2a<0}}
    Also folgt mit der besagten Ungleichung und wegen x^{3}>a>0:
    x^{3}\left(1-{\frac {x^{3}-a}{3x^{3}}}\right)^{3}\geq x^{3}\left(1-3\cdot {\frac {x^{3}-a}{3x^{3}}}\right)=x^{3}-(x^{3}-a)=a
    Zweite Ungleichung: Mittels vollständiger Induktion über n:
    Induktionsanfang: n=0. x_{0}^{3}\geq a nach Voraussetzung.
    Induktionsschritt: n\to n+1. x_{{n+1}}^{3}=\left(x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}\right)^{3}\geq a nach der ersten Ungleichung, da nach der Induktionsvoraussetzung x_{n}^{3}>a gilt.
  2. (x_{n}) ist monoton fallend: Es gilt
    x_{{n+1}}-x_{n}=x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}-x_{n}=-{\frac {\overbrace {x_{n}^{3}-a}^{{>0}}}{\underbrace {3x_{n}^{2}}_{{>0}}}}<0
    (x_{n}) ist nach unten beschränkt: Wegen x_{n}^{3}\geq a folgt sofort
    x_{n}\geq {\sqrt[ {3}]{a}}
  3. Da (x_{n}) nach 2. monoton fallend und nach unten beschränkt ist, folgt mit dem Monotoniekriterium die Konvergenz der Folge. Setzen wir \lim _{{n\to \infty }}x_{n}=\lim _{{n\to \infty }}x_{{n+1}}=x, so gilt mit der rekursiven Definition der Folge (x_{n}):
    x-{\frac {x^{3}-a}{3x^{2}}}=x\iff {\frac {x^{3}-a}{3x^{2}}}=0\iff x^{3}-a=0\iff x^{3}=a\iff x={\sqrt[ {3}]{a}}
Hinweis:
Analog lässt sich allgemein für jede natürliche Zahl k\geq 2 und für reelle Zahlen x_{0}>0 und a>0 zeigen, dass die rekursiv definierte Folge (x_{n})_{{n\in \mathbb{N} }} mit
x_{{n+1}}={\frac 1k}\left((k-1)x_{n}-{\frac {a}{x_{n}^{{k-1}}}}\right)
gegen {\sqrt[ {k}]{a}} konvergiert.