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

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 {1}{2}}a_{n}+{\tfrac {1}{2}}$ 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 {1}{2}}a_{0}+{\frac {1}{2}}={\frac {1}{2}}\cdot 0+{\frac {1}{2}}={\frac {1}{2}}\\[0.3em]a_{2}&={\frac {1}{2}}a_{1}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {1}{2}}+{\frac {1}{2}}={\frac {3}{4}}\\[0.3em]a_{3}&={\frac {1}{2}}a_{2}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {3}{4}}+{\frac {1}{2}}={\frac {7}{8}}\\[0.3em]a_{4}&={\frac {1}{2}}a_{3}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {7}{8}}+{\frac {1}{2}}={\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 {1}{2}}\\[0.3em]f(2)&={\frac {3}{4}}\\[0.3em]f(3)&={\frac {7}{8}}\\[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 {1}{2}}&={\frac {2^{1}-1}{2^{1}}}\\[0.3em]f(2)&={\frac {3}{4}}&={\frac {2^{2}-1}{2^{2}}}\\[0.3em]f(3)&={\frac {7}{8}}&={\frac {2^{3}-1}{2^{3}}}\\[0.3em]&\vdots \end{array}}\end{aligned}}$

Anhand dieser Beispiele liegt die Vermutung nahe, dass wir $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 {1}{2}}\right)^{0}$

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

${\begin{aligned}a_{n+1}&={\frac {1}{2}}{\color {Teal}a_{n}}+{\frac {1}{2}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung}}\right.}\\[0.3em]&={\frac {1}{2}}\cdot {\color {Teal}\left(1-\left({\frac {1}{2}}\right)^{n}\right)}+{\frac {1}{2}}\\[0.3em]&={\frac {1}{2}}-\left({\frac {1}{2}}\right)^{n+1}+{\frac {1}{2}}\\[0.3em]&=1-\left({\frac {1}{2}}\right)^{n+1}\end{aligned}}$

Damit haben wir $a_{n}=1-\left({\frac {1}{2}}\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 {1}{2}}\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 {1}{2}}\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 {1}{2}}\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 {1}{2}}a_{n-1}+{\frac {1}{2}}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 {1}{2}}a_{n-1}+{\frac {1}{2}}a_{n-2}-a_{n-1}\\&={\frac {1}{2}}a_{n-2}-{\frac {1}{2}}a_{n-1}\\&={\frac {1}{2}}(a_{n-2}-a_{n-1})\\&=-{\frac {1}{2}}(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 {1}{2}}(a_{n-1}-a_{n-2})\\&=-{\frac {1}{2}}\left({\frac {1}{2}}a_{n-2}+{\frac {1}{2}}a_{n-3}-a_{n-2}\right)\\&=-{\frac {1}{2}}\left({\frac {1}{2}}a_{n-3}-{\frac {1}{2}}a_{n-2}\right)\\&=\left(-{\frac {1}{2}}\right)^{2}(a_{n-2}-a_{n-3})\end{aligned}}$

In jedem Schritt kommt also $-{\tfrac {1}{2}}$ als Vorfaktor hinzu. Nach insgesamt $n-1$ Schritten erhalten wir

$a_{n}-a_{n-1}=\left(-{\frac {1}{2}}\right)^{n-1}\underbrace {(a_{1}-a_{0})} _{=1}=\left(-{\frac {1}{2}}\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 {1}{2}}\right)^{k-1}=\sum _{k=0}^{n-1}\left(-{\frac {1}{2}}\right)^{k}={\frac {1-(-{\frac {1}{2}})^{n}}{1-(-{\frac {1}{2}})}}={\frac {1-(-{\frac {1}{2}})^{n}}{\frac {3}{2}}}={\tfrac {2}{3}}(1-(-{\tfrac {1}{2}})^{n})$

Damit erhalten wir die explizite Darstellung

$a_{n}={\tfrac {2}{3}}(1-(-{\tfrac {1}{2}})^{n})$

Mit $\lim _{n\to \infty }(-{\tfrac {1}{2}})^{n}=0$ und den Rechenregeln für Folgen gilt

$\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\tfrac {2}{3}}(1-(-{\tfrac {1}{2}})^{n})={\tfrac {2}{3}}(1-0)={\tfrac {2}{3}}$

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 {1}{2}}a_{0}+{\frac {1}{2}}={\frac {1}{2}}\cdot 0+{\frac {1}{2}}={\frac {1}{2}}\\[0.3em]a_{2}&={\frac {1}{2}}a_{1}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {1}{2}}+{\frac {1}{2}}={\frac {3}{4}}\\[0.3em]a_{3}&={\frac {1}{2}}a_{2}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {3}{4}}+{\frac {1}{2}}={\frac {7}{8}}\\[0.3em]a_{4}&={\frac {1}{2}}a_{3}+{\frac {1}{2}}={\frac {1}{2}}\cdot {\frac {7}{8}}+{\frac {1}{2}}={\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 {1}{2}}a_{0}+{\frac {1}{2}}={\frac {1}{2}}\cdot 0+{\frac {1}{2}}={\frac {1}{2}}\geq 0=a_{0}$

Der Induktionsschritt von $n$ nach $n+1$ ist:

${\begin{aligned}a_{n+1}&={\frac {1}{2}}{\color {Teal}a_{n}}+{\frac {1}{2}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung: }}a_{n}\geq a_{n-1}\right.}\\[0.3em]&\geq {\frac {1}{2}}{\color {Teal}a_{n-1}}+{\frac {1}{2}}=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 {1}{2}}{\color {Teal}a_{n}}+{\frac {1}{2}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Induktionsvoraussetzung: }}a_{n}\leq 1\right.}\\[0.3em]&\leq {\frac {1}{2}}{\color {Teal}1}+{\frac {1}{2}}=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 {1}{2}}a_{n}+{\frac {1}{2}}\right.}\\[0.5em]&=\lim _{n\to \infty }{\frac {1}{2}}a_{n}+{\frac {1}{2}}\\[0.5em]&{\color {OliveGreen}\left\downarrow \ {\text{Grenzwertsätze}}\right.}\\[0.5em]&=\left(\lim _{n\to \infty }{\frac {1}{2}}\right)\cdot \left(\lim _{n\to \infty }a_{n}\right)+\lim _{n\to \infty }{\frac {1}{2}}\\[0.5em]&={\frac {1}{2}}a+{\frac {1}{2}}\end{aligned}}$

Der Wert $a$ muss damit die Gleichung $a={\tfrac {1}{2}}a+{\tfrac {1}{2}}$ erfüllen. Aufgrund dieser Bedingung können wir den exakten Wert von $a$ bestimmen:

$a={\frac {1}{2}}a+{\frac {1}{2}}\iff {\frac {1}{2}}a={\frac {1}{2}}\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

Aufgabe (Grenzwert einer rekursiv definierten 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

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

${\begin{aligned}a_{0}&=2\\[0.3em]a_{1}&=2-{\frac {1}{2}}={\frac {3}{2}}\\[0.3em]a_{2}&=2-{\frac {1}{\frac {3}{2}}}=2-{\frac {2}{3}}={\frac {4}{3}}\\[0.3em]a_{3}&=2-{\frac {1}{\frac {4}{3}}}=2-{\frac {3}{4}}={\frac {5}{4}}\\[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$:

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb {N}$ bewiesen werden soll:

$a_{n}={\frac {n+2}{n+1}}$

1. Induktionsanfang:

Für $n=0$ ist $a_{0}={\tfrac {0+2}{0+1}}=2$.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$a_{n}={\frac {n+2}{n+1}}$

2b. Induktionsbehauptung:

$a_{n+1}={\frac {n+3}{n+2}}$

2c. 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 {2}{n}}}{1+{\frac {1}{n}}}}={\frac {1}{1}}=1$

Lösung 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$:

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb {N}$ bewiesen werden soll:

$a_{n+1}\leq a_{n}$

1. Induktionsanfang:

$a_{1}=2-{\frac {1}{a_{0}}}=2-{\frac {1}{2}}={\frac {3}{2}}\leq 2=a_{0}$

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$a_{n+1}\leq a_{n}$

2b. Induktionsbehauptung:

$a_{n+2}\leq a_{n+1}$

2c. 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:

Aussageform, deren Allgemeingültigkeit für $n\in \mathbb {N}$ bewiesen werden soll:

$a_{n}\geq 1$

1. Induktionsanfang:

$a_{0}=2\geq 1$

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

$a_{n}\geq 1$

2b. Induktionsbehauptung:

$a_{n+1}\geq 1$

2c. 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 {1}{a}}\\[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

Aufgabe (Konvergenz einer rekursiv definierenten Folge berechnen)

Gegeben sei die rekursiv definierte Folge

${\begin{aligned}a_{0}&=0\\a_{1}&=2\\a_{n}&={\frac {1}{3}}a_{n-1}+{\frac {2}{3}}a_{n-2}\end{aligned}}$

1. Begründe, warum diese Folge konvergiert, und berechne dessen Grenzwert.
2. Was passiert bei den Startwerten $a_{0}=a_{1}=1$?

Lösung (Konvergenz einer rekursiv definierenten Folge berechnen)

Lösung Teilaufgabe 1:

Es gilt

${\begin{aligned}a_{n}-a_{n-1}&={\frac {1}{3}}a_{n-1}+{\frac {2}{3}}a_{n-2}-a_{n-1}\\&={\frac {2}{3}}a_{n-2}-{\frac {2}{3}}a_{n-1}\\&={\frac {2}{3}}(a_{n-2}-a_{n-1})\\&=-{\frac {2}{3}}(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 {2}{3}}(a_{n-1}-a_{n-2})\\&=\left(-{\frac {2}{3}}\right)^{2}(a_{n-2}-a_{n-3})\\&=\ldots \\&=\left(-{\frac {2}{3}}\right)^{n-1}\underbrace {(a_{1}-a_{0})} _{=2}\\&=2\cdot \left(-{\frac {2}{3}}\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 {2}{3}}\right)^{k-1}\\&=2\cdot \sum _{k=0}^{n-1}\left(-{\frac {2}{3}}\right)^{k}\\&=2\cdot {\frac {1-(-{\frac {2}{3}})^{n}}{1-(-{\frac {2}{3}})}}\\&=2\cdot {\frac {1-(-{\frac {2}{3}})^{n}}{\frac {5}{3}}}\\&=2\cdot {\tfrac {3}{5}}(1-(-{\tfrac {2}{3}})^{n})\\&={\tfrac {6}{5}}\cdot (1-(-{\tfrac {2}{3}})^{n})\end{aligned}}$

Mit $\lim _{n\to \infty }(-{\tfrac {2}{3}})^{n}=0$ und den Rechenregeln für Folgen gilt

$\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }{\frac {6}{5}}(1-(-{\frac {2}{3}})^{n})={\frac {6}{5}}(1-0)={\frac {6}{5}}$

Lösung Teilaufgabe 2:

Für $a_{0}=1$ und $a_{1}=1$ bekommt man durch Einsetzen:

$a_{2}={\frac {1}{3}}\cdot 1+{\frac {2}{3}}\cdot 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\in \mathbb {N}$ bewiesen werden soll:

$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:

2a. Induktionsvoraussetzung:

$a_{n}=1$

2b. Induktionsbehauptung:

$a_{n+1}=1$

2c. Beweis des Induktionsschritts:

$a_{n+1}={\frac {1}{3}}\cdot a_{n}+{\frac {2}{3}}a_{n-1}{\overset {\text{IV}}{=}}{\frac {1}{3}}\cdot 1+{\frac {2}{3}}\cdot 1=1$

Damit gilt auch $\lim _{n\to \infty }a_{n}=\lim _{n\to \infty }1=1$.

Anwendungsbeispiel: Babylonisches oder Heronisches Wurzelziehen

Die ersten Folgeglieder der babylonischen Wurzelfolgen zur Berechnung von ${\sqrt {2}}$ mit den Startwerten $x_{0}=2$, $x_{0}=4$ und $x_{0}=8$.

Die Folgenglieder der babylonischen Wurzelfolge mit dem Startwert $a_{0}={\tfrac {1}{4}}$.

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 {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\end{aligned}}$

Dann konvergiert $(x_{n})_{n\in \mathbb {N} }$ gegen ${\sqrt {a}}$.

Folgenglieder 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 (Babylonische Wurzelfunktion)

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 {1}{2}}\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 {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.5em]&={\frac {1}{2}}\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 {1}{2}}\left(x_{n}+{\frac {a}{x_{n}}}\right)\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{Grenzwertsätze}}\right.}\\[0.3em]&={\frac {1}{2}}\left(\lim _{n\to \infty }x_{n}+{\frac {a}{\lim _{n\to \infty }x_{n}}}\right)\\[0.3em]&={\frac {1}{2}}\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 {1}{2}}\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

Aufgabe (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 {1}{3}}\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 Bernoullischen Ungleichung: 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})$.

Lösung (Rekursionsfolge für dritte Wurzel)

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: Sei $n\in \mathbb {N}$. Wir wissen aus 1., dass $x_{n}^{3}-a>0$. Daraus folgt auch, dass $x_{n}\neq 0$ und damit $3x_{n}^{2}>0$. Folglich gilt
   ${\begin{aligned}&\ x_{n+1}-x_{n}\\[0.3em]=&\ x_{n}-{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}-x_{n}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\text{rekrusive Definition von }}x_{n+1}\right.}\\[0.3em]=&\ -{\frac {x_{n}^{3}-a}{3x_{n}^{2}}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ x_{n}^{3}-a>0{\text{ und }}3x_{n}^{2}>0\right.}\\[0.3em]<&\ 0.\end{aligned}}$

   Also gilt $x_{n+1}<x_{n}$.

   $(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 {1}{k}}\left((k-1)x_{n}-{\frac {a}{x_{n}^{k-1}}}\right)$

gegen ${\sqrt[{k}]{a}}$ konvergiert.