Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz

05.02.2015, 19:56

Tempi

Auf diesen Beitrag antworten »

Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz

Hi,
vollständige Induktion bei Summenzeichen oder auch Ableitungen bekomme ich noch irgendwie hin, aber bei rekursiv definierten Folgen schaltet irgendwie mein Gehirn aus.
Ich trage das schon ein paar Tage mit mir herum und finde einfach nichts das mir weiterhilft. Ich habe noch kein einzige Aufgabe dieser Art gelöst.

Also...
$\begin{eqnarray*} x_{n+1}= 3x_{n+1}^2+\frac{1}{12} \end{eqnarray*}$ mit Startwert $\begin{eqnarray*} x_{0}=0 \end{eqnarray*}$

Ich soll mit vollständiger Induktion zeigen, dass für alle $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ gilt $\begin{eqnarray*} x_{n} < \frac{1}{6} \end{eqnarray*}$
___________________________________________________________________
$\begin{eqnarray*} Induktionsanfang: \end{eqnarray*}$ "prüfen, ob es für das kleinste $\begin{eqnarray*} n \end{eqnarray*}$ gilt"

$\begin{eqnarray*} x_{0}=0 \end{eqnarray*}$ $\begin{eqnarray*} <\frac{1}{6} \end{eqnarray*}$ gilt

$\begin{eqnarray*} Induktionsschritt: \end{eqnarray*}$
Induktionsbehauptung: "aus Aufgabenstellung abschreiben"
$\begin{eqnarray*} x_{n+1}< \frac{1}{6} \end{eqnarray*}$

Induktionsvoraussetzung:
$\begin{eqnarray*} ??? \end{eqnarray*}$
Beweis:
$\begin{eqnarray*} ??? \end{eqnarray*}$
___________________________________________________________________

So zu aller erst was ist denn jetzt die I.-Voraussetzung? verwirrt

verwirrt

$\begin{eqnarray*} x_{0} < \frac{1}{6} \end{eqnarray*}$ ??? Irgendwie hab ich hier den Hänger und 0 Ahnung wie ich ansetzen soll, auch dann beim Beweis nicht.

05.02.2015, 20:01

Helferlein

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
Könntest Du die Aufgabenstellung bitte korrigieren?
Eine Rekursion hast Du nämlich nicht vorliegen, da nur der Index n+1 in der Definition auftaucht und keine niedrigeren Indizes.

05.02.2015, 20:11

Tempi

Auf diesen Beitrag antworten »

Also ie exakte Aufgabenstellung lautet :

Gegeben ist die rekursive Folge $\begin{eqnarray*} x_{n+1}=3x_{n}^2+\frac{1}{12} \end{eqnarray*}$ mit dem Startwert $\begin{eqnarray*} x_{0} = 0 \end{eqnarray*}$

Zeigen Sie mit vollständiger Induktion: Für alle $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ gilt $\begin{eqnarray*} x_{n} < \frac{1}{6} \end{eqnarray*}$

05.02.2015, 20:18

Matt Eagle

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
Offenbar geht's hier um die Rekursion:

$\begin{eqnarray*} x_{n+1}=x_n^2+\frac 1{12}\text{ mit }x_0=0. \end{eqnarray*}$

Die Beschränktheit nach oben durch $\begin{eqnarray*} \frac 16 \end{eqnarray*}$ zeigst Du mit einer einfachen Induktion. Ohne Tricks oder so, einfach stumpf geradeaus...

Für den Nachweis des monotonen Wachsens ist es ganz nützlich zu sehen, dass:

$\begin{eqnarray*} x_{n+1}-x_n=3\left(x_n-\frac 16\right)^2. \end{eqnarray*}$

05.02.2015, 20:21

Matt Eagle

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
Uups, zu langsam.
Inzwischen ist die Aufgabenstellung also geklärt und ich bin wieder raus. Wink

Wink

05.02.2015, 20:54

Matt Eagle

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
Grad ist mir aufgefallen, dass ich in meinem Beitrag vorhin den Faktor $\begin{eqnarray*} 3 \end{eqnarray*}$ bei der Rekursionsvorschrift verbummelt habe. Sorry!

Bei der Gelegenheit noch ein kleiner Schubser, um die Induktion ins Rollen zu bringen:

Der Induktionsanfang ist ja klar.

Induktionsvoraussetzung: Sei die Beh. für $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ bereits bewiesen, d.h.: Sei $\begin{eqnarray*} x_n<\frac 16. \end{eqnarray*}$

Im Induktionsschritt (von n->n+1) ist dann nur noch zu zeigen, dass die Induktionsvoraussetzung impliziert, dass $\begin{eqnarray*} x_{n+1}<\frac 16. \end{eqnarray*}$

Anzeige

05.02.2015, 21:13

Tempi

Auf diesen Beitrag antworten »

Also ich muss in der Induktionsvoraussetzung annehmen, dass das was ich laut Aufgabenstellung zeigen soll bereits bewiesen ist? verwirrt

verwirrt

05.02.2015, 21:44

Helferlein

Auf diesen Beitrag antworten »

Nein. Du sollst zeigen, dass die Aussage für n+1 gilt, sofern sie für ein bestimmtes n gilt.

06.02.2015, 09:44

Tempi

Auf diesen Beitrag antworten »

Wie schaut es hiermit aus? verwirrt

verwirrt

$\begin{eqnarray*} Beweis: \end{eqnarray*}$
$\begin{eqnarray*} x_{n+1} =3x^2_{n} +\frac{1}{12} <br /> \Rightarrow x_{0+1} = 3x_{0}^{2}+\frac{1}{12} \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow x_{1} =\frac{1}{12} <\frac{1}{6} \end{eqnarray*}$

06.02.2015, 10:14

klarsoweit

Auf diesen Beitrag antworten »

Jetzt hast du nur gezeigt, daß x_1 < 1/6 ist. Das ist aber keine vollständige Induktion. Was beim Induktionsschritt zu tun hast, hat Matt Eagle in seinem letzten Beitrag gesagt.

Zitat:

Original von Tempi
Also ich muss in der Induktionsvoraussetzung annehmen, dass das was ich laut Aufgabenstellung zeigen soll bereits bewiesen ist? verwirrt

verwirrt

Im Gegensatz zu Helferlein würde ich zu dieser Aussage nicken.
Beim Induktionsschritt ist die Implikation A(n) ==> A(n+1) zu zeigen, wobei A(n) die zu beweisende Aussage ist. Insofern wird im Induktionsschritt die Aussage A(n) als wahr vorausgesetzt.

06.02.2015, 10:49

Tempi

Auf diesen Beitrag antworten »

Kann man das folgende so als Allgemeinaussage stehen lassen für rekursive Folgen? In der Rekursionformel einfach immer $\begin{eqnarray*} n \end{eqnarray*}$ mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ ersetzen damit sowas wie $\begin{eqnarray*} a_{((n+1)+1)}= ... a_{n+1}... \end{eqnarray*}$ herauskommt?

Konkret zur Aufgabe:
$\begin{eqnarray*} x_{(n+1)+1} =3a_{n+1} +\frac{1}{12} \end{eqnarray*}$

06.02.2015, 10:56

klarsoweit

Auf diesen Beitrag antworten »

Wenn, dann $\begin{eqnarray*} x_{(n+1)+1} =3x_{n+1} +\frac{1}{12} \end{eqnarray*}$ , ansonsten: ja. smile

smile

06.02.2015, 11:06

Tempi

Auf diesen Beitrag antworten »

Äh ja ich meinte natürlich $\begin{eqnarray*} x_{(n+1)+1} =3x_{n+1}^2 +\frac{1}{12} \end{eqnarray*}$

Nur wie führe ich jetzt den Beweis durch? Ist bei vollständiger Induktion mit rekursiven Folgen im Vergleich zu Induktion mit Summen, Teilbarkeit, etc. mehr Argumentation bzw. Überlegung statt Rechnerei notwenig?
Also z.B da $\begin{eqnarray*} 0<x_n<\frac{1}{6} \Rightarrow x_n^2<\frac{1}{6} \end{eqnarray*}$ und ähm ja irgendwie sowas in der Richtung? verwirrt

verwirrt

06.02.2015, 11:51

Matt Eagle

Auf diesen Beitrag antworten »

Zitat:

Original von Tempi
Nur wie führe ich jetzt den Beweis durch?

Das wurde doch schon mehrfach deutlich gesagt.

Zitat:

Original von Tempi
Ist bei vollständiger Induktion mit rekursiven Folgen im Vergleich zu Induktion mit Summen, Teilbarkeit, etc. mehr Argumentation bzw. Überlegung statt Rechnerei notwenig?

Nein, warum sollte das auch so sein? Der Induktion ist doch die Aussage, zu deren Beweis sie herangezogen wird, vollkommen egal.

Offenbar hast Du das grundsätzliche Prinzip der Vollständigen Induktion noch nicht so ganz verinnerlicht.

Im Grunde genommen beweist Du im Induktionsschritt einfach folgendes:

Gilt eine Aussage für ein $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ , dann gilt sie auch für den Nachfolger $\begin{eqnarray*} n+1 \end{eqnarray*}$ .

Wenn du dieses allgemein gezeigt hast dann folgt zusammen mit dem Induktionsanfang für $\begin{eqnarray*} n_0 \end{eqnarray*}$ die Gültigkeit der Aussage für alle $\begin{eqnarray*} n\geq n_0 \end{eqnarray*}$ .

Im konkreten Fall musst Du also zeigen, dass Du aus der VORAUSSETZUNG $\begin{eqnarray*} x_n<\frac 16 \end{eqnarray*}$ folgern kannst, dass auch $\begin{eqnarray*} x_{n+1}<\frac 16. \end{eqnarray*}$

Um diesen Beweis nun zu führen ist nichts weiter zu tun als einmal die Rekursionsformel hinzuschreiben und in dieser dann die vorausgesetzte Ungleichung einzubringen, dann steht's eigentlich direkt da.

06.02.2015, 11:52

klarsoweit

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
In Ergänzung zum Beitrag von Matt Eagle:

Als erstes könntest du in der linken Seite von $\begin{eqnarray*} x_{n+1} < \frac 16 \end{eqnarray*}$ die Rekursionsvorschrift einsetzen.

06.02.2015, 12:23

Tempi

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
Okay also die Rekursionsvorschrift $\begin{eqnarray*} x_{n+1} =3x^2_{n} +\frac{1}{12}<br /> \end{eqnarray*}$ einsetzen:
$\begin{eqnarray*} x_{n+1}<\frac{1}{6} \end{eqnarray*}$
$\begin{eqnarray*} 3x_{n+1}^2 +\frac{1}{12}<\frac{1}{6} \end{eqnarray*}$

Und jetzt nur noch nach $\begin{eqnarray*} x_{n+1} \end{eqnarray*}$ auflösen?

06.02.2015, 12:35

klarsoweit

Auf diesen Beitrag antworten »

RE: Rekursive Folge - Vollständige Induktion, Monotonie, Konvergenz
Anscheinend ist es über alle Maßen schwer, in $\begin{eqnarray*} x_{n+1}<\frac{1}{6} \end{eqnarray*}$ das $\begin{eqnarray*} x_{n+1} \end{eqnarray*}$ durch $\begin{eqnarray*} 3x^2_{n} +\frac{1}{12} \end{eqnarray*}$ zu ersetzen. unglücklich

unglücklich

Richtig ist: $\begin{eqnarray*} 3x_n^2 +\frac{1}{12}<\frac{1}{6} \end{eqnarray*}$ <-- dieses ist also zu zeigen.

Jetzt solltest du die linke Seite hernehmen und das x_n mittels der Induktionsvoraussetzung nach oben abschätzen.

06.02.2015, 12:53

Tempi

Auf diesen Beitrag antworten »

Upps das $\begin{eqnarray*} n+1 \end{eqnarray*}$ sollte natürlich nur ein $\begin{eqnarray*} n \end{eqnarray*}$ sein. Ich sollte mal weniger copy&paste in dem Formeleditor benutzen. Tut mir Leid wenn ich durch mein Unwissen manchmal vielleicht offensichtliche Dinge nicht erkenne unglücklich

unglücklich

Die Induktionsvoraussetzung ist $\begin{eqnarray*} x_n<\frac16 \end{eqnarray*}$

Wie funktioniert das mit dem nach oben abschätzen? Kommt jetzt etwas für das ich sowas hier benötige?
$\begin{eqnarray*} 0<x_n<\frac{1}{6} \Rightarrow x_n^2<\frac{1}{6} \end{eqnarray*}$

06.02.2015, 13:12

klarsoweit

Auf diesen Beitrag antworten »

Richtig ist: $\begin{eqnarray*} 0<x_n<\frac{1}{6} \Rightarrow x_n^2<\frac{1}{36} \end{eqnarray*}$
Jetzt multipliziere noch die rechte Ungleichung mit 3 und dann bist du fast schon am Ziel. smile

smile

06.02.2015, 14:54

Tempi

Auf diesen Beitrag antworten »

Wenn ich die rechte Seite mit 3 multipliziere, muss ich dann nicht auch $\begin{eqnarray*} +\frac{1}{12} \end{eqnarray*}$ machen?

06.02.2015, 15:04

klarsoweit

Auf diesen Beitrag antworten »

Genau. Deswegen sagte ich ja auch "fast schon am Ziel". Augenzwinkern

Augenzwinkern

06.02.2015, 15:39

Tempi

Auf diesen Beitrag antworten »

Okay wenn ich das mache steht da
$\begin{eqnarray*} x_n^2< \frac{1}{36}*3+\frac{1}{12}<br /> \Rightarrow x_n^2< \frac{1}{6}<br /> \end{eqnarray*}$

Aber ich will doch zeigen, dass $\begin{eqnarray*} x_{n+1}<\frac{1}{6} \end{eqnarray*}$ ist? Irgendwo häng ich gerade noch oder anders gesagt wie füge ich die ganzen Schritte denn jetzt zusammen die ich gemacht habe?

06.02.2015, 16:34

Matt Eagle

Auf diesen Beitrag antworten »

Statt Dir jetzt die Lösung hinzuknallen versuch ich's noch mal anders.

Sei $\begin{eqnarray*} a<\frac 16\text{ und }b:=3a^2+\frac 1{12}. \end{eqnarray*}$

Zeige: $\begin{eqnarray*} b<\frac 1{12}. \end{eqnarray*}$

Hättest Du eine Idee wie Du das beweisen könntest?

06.02.2015, 17:00

Tempi

Auf diesen Beitrag antworten »

Du meinst $\begin{eqnarray*} b<\frac 1{6} \end{eqnarray*}$ ?

Damit $\begin{eqnarray*} b<\frac{1}{6} \end{eqnarray*}$ ist muss ja $\begin{eqnarray*} 3a^2+\frac 1{12}<\frac{1}{6} \end{eqnarray*}$ sein.

Ich würde dann einfach diese Gleichung umstellen:
$\begin{eqnarray*} 3a^2+\frac 1{12}<\frac{1}{6} \end{eqnarray*}$
$\begin{eqnarray*} \Leftrightarrow 3a^2<\frac{1}{6}-\frac 1{12} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow a^2<\frac{\frac{1}{6}-\frac {1}{12}}{3} \end{eqnarray*}$

$\begin{eqnarray*} \Leftrightarrow a<\sqrt{\frac{\frac{1}{6}-\frac {1}{12}}{3}}=\frac{1}{6} \end{eqnarray*}$

Also ist $\begin{eqnarray*} b<\frac{1}{6} \end{eqnarray*}$ für $\begin{eqnarray*} a<\frac{1}{6} \end{eqnarray*}$

06.02.2015, 17:15

Matt Eagle

Auf diesen Beitrag antworten »

Zitat:

Original von Tempi
Du meinst $\begin{eqnarray*} b<\frac 1{6} \end{eqnarray*}$ ?

Ja, sicher! Da hab ich gepennt - sorry!

Deine folgenden Ausführungen sind nicht besonders suggestiv aufgeschrieben.
Dieses Rumhantieren mit Äquivalenzen (die teilweise keine sind und die Du hier gar nicht brauchst) bis Du dann irgendwie bei einer wahren Aussage landest, wirkt sehr ungelenk und ist zudem extrem fehleranfällig.

Besser wäre es z.B. so:

$\begin{eqnarray*} b=3a^2+\frac 1{12}< 3\left(\frac 16\right)^2+\frac 1{12}=\frac 3{36}+\frac 1{12}=\frac 16. \end{eqnarray*}$

oder so:

$\begin{eqnarray*} a<\frac 16\Rightarrow a^2<\frac 1{36}\Rightarrow 3a^2+\frac 1{12}<\frac 3{36}+\frac 1{12}\Rightarrow b<\frac 16. \end{eqnarray*}$

Und funkt's jetzt?

06.02.2015, 18:15

Tempi

Auf diesen Beitrag antworten »

Okay ich versuche dann jetzt nochmal den kompletten Beweis richtig aufzuschreiben:

$\begin{eqnarray*} x_{n+1}=3x_{n}^2+\frac{1}{12}; x_0 = 0 \end{eqnarray*}$

$\begin{eqnarray*} Induktionsanfang: <br /> n=0: x_{0}=0<\frac{1}{6} \end{eqnarray*}$

$\begin{eqnarray*} Induktionsschritt: \end{eqnarray*}$
Angenommen für ein festes aber beliebiges $\begin{eqnarray*} n\in \mathbb N \end{eqnarray*}$ gilt $\begin{eqnarray*} x_n < \frac{1}{6} \end{eqnarray*}$ (Induktionsvoraussetzung) dann gilt auch $\begin{eqnarray*} x_{n+1} < \frac{1}{6} \end{eqnarray*}$ (Induktionsbehauptung)

$\begin{eqnarray*} Beweis: \end{eqnarray*}$

$\begin{eqnarray*} x_{n}<\frac{1}{6} \Rightarrow x_{n} ^2<\frac{1}{36}\Rightarrow 3x_{n}^2 <3\frac{1}{36} \Rightarrow3x_{n}^2 +\frac{1}{12} <3\frac{1}{36} +\frac{1}{12} = \frac{1}{6}\Rightarrow x_{n-1}<\frac{1}{6} \end{eqnarray*}$

06.02.2015, 18:21

Matt Eagle

Auf diesen Beitrag antworten »

Ja, so kann man das aufschreiben - abgesehen vom kleinen Tippfehler am Ende.
(Ich meine das n-1 im Index)

In solchen Situationen spricht man auch gerne von einer schweren Geburt Augenzwinkern

Augenzwinkern

06.02.2015, 19:03

Tempi

Auf diesen Beitrag antworten »

Vielen Dank schon mal bis hier her Freude

Freude

Wie zeige ich jetzt, dass die Folge streng monoton ist ohne die einzelnen Folgenwerte per Hand auszurechnen?

06.02.2015, 19:23

Matt Eagle

Auf diesen Beitrag antworten »

Auch das wurde schon erwähnt...

Zitat:

Original von Matt Eagle
Für den Nachweis des monotonen Wachsens ist es ganz nützlich zu sehen, dass:

$\begin{eqnarray*} x_{n+1}-x_n=3\left(x_n-\frac 16\right)^2. \end{eqnarray*}$

06.02.2015, 20:46

Tempi

Auf diesen Beitrag antworten »

Das kann ich jetzt so auf die schnelle überhaupt nicht nachvollziehen

09.02.2015, 08:31

klarsoweit

Auf diesen Beitrag antworten »

Wann ist denn eine Folge treng monoton wachsend?

Zitat:

Original von Tempi
$\begin{eqnarray*} 3x_{n}^2 +\frac{1}{12} <3\frac{1}{36} +\frac{1}{12} = \frac{1}{6}\Rightarrow x_{n-1}<\frac{1}{6} \end{eqnarray*}$

Richtig ist: $\begin{eqnarray*} 3x_{n}^2 +\frac{1}{12} <3\frac{1}{36} +\frac{1}{12} = \frac{1}{6}\Rightarrow x_{n+1}<\frac{1}{6} \end{eqnarray*}$

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »