Induktion bei rekursiver Folge?

27.05.2010, 21:01

kevin89

Auf diesen Beitrag antworten »

Induktion bei rekursiver Folge?

Hallöchen.

Stelle mir grad die Frage ob ich durch Induktion beweisen kann, dass

$\begin{eqnarray*} a_{n} = 1+ \frac{1}{3-a_{n-1} } \end{eqnarray*}$ immer $\begin{eqnarray*} \leq 2 \end{eqnarray*}$ ist.

Oder ist Induktion bei rekursiven Folgen nicht erlaubt?

MfG

27.05.2010, 21:04

lgrizu

Auf diesen Beitrag antworten »

RE: Induktion bei rekursiver Folge?

Zitat:

Original von kevin89

Oder ist Induktion bei rekursiven Folgen nicht erlaubt?

MfG

warum sollte das nicht erlaubt sein?

27.05.2010, 21:07

kevin89

Auf diesen Beitrag antworten »

Keine Ahnung Big Laugh

Big Laugh

Irgendjemand hatte mir so 'nen Floh ins Ohr gesetzt.
Dann mach ich mich mal da ran ^^

27.05.2010, 21:10

lgrizu

Auf diesen Beitrag antworten »

wenn du probleme hast, einfach melden, wie ist denn der startwert deiner folge?

27.05.2010, 21:28

kevin89

Auf diesen Beitrag antworten »

Also habs mal versucht, schien gar nicht so schwer, kann aber auch falsch sein^^

Also:
Gegeben ist:
$\begin{eqnarray*} a_{1}=1 , a_{n} = 1+ \frac{1}{3-a_{n-1} } \end{eqnarray*}$

Nun IA für n=2:

---> $\begin{eqnarray*} a_{2}=\frac {3}{2} \leq 2 \end{eqnarray*}$ ist korrekt.

IV: Sei $\begin{eqnarray*} a_{n} = 1+ \frac{1}{3-a_{n-1} } \end{eqnarray*}$ für ein n € |N bewiesen.

IS: n-->n+1

$\begin{eqnarray*} 2\geq a_{n+1} = 1+ \frac{1}{3-a_{n} } \end{eqnarray*}$
Nach Voraussetzung ist $\begin{eqnarray*} a_{n} \leq 2 \end{eqnarray*}$ also maximal 2.

$\begin{eqnarray*} \Rightarrow nach IV: 2\geq 1+ \frac{1}{3-2} = 2 \end{eqnarray*}$
Also wäre die Aussage bewiesen.

Geht das so? Oder os da irgendwo ein Fehler drin?

27.05.2010, 21:35

Airblader

Auf diesen Beitrag antworten »

Zitat:

Original von kevin89
IV: Sei $\begin{eqnarray*} a_{n} = 1+ \frac{1}{3-a_{n-1} } \end{eqnarray*}$ für ein n € |N bewiesen.

Das ist ja wohl Unsinn.

Dein Induktionsschritt ist ... nicht gerade astrein.
Es fehlt eine Begründung, warum du einfach die '2' einsetzen darfst. Ist es dir überhaupt selbst klar?

Auch ist es unsauber, mit dem anzufangen, was du beweisen sollst. Nimm lieber das (n+1)-te Folgenglied, schätze es mit der (korrekten) Induktionsannahme ab und zeige, dass es kleiner gleich zwei ist. Die konkreten Schritte, sofern sauber begründet, bleiben dabei prinzipiell gleich.

air

Anzeige

27.05.2010, 21:38

lgrizu

Auf diesen Beitrag antworten »

ist nicht ganz richtig so weit.
beim induktionsschluss nicht einfach die zwei einsetzen:

nach IV ist $\begin{eqnarray*} a_n \leq 2 \Rightarrow \frac{1}{3-a_n} \leq 1 \Rightarrow 1+\frac{1}{3-a_n} \leq 2 \end{eqnarray*}$

27.05.2010, 21:39

Airblader

Auf diesen Beitrag antworten »

@ Igrizu

Sorry, wollte nicht reinfunken. Du stehst bei mir als offline drin. Sehe aber auch gerade, dass du keine Angabe über die letzte Aktivität freischaltest. The topic is yours. Augenzwinkern

Augenzwinkern

air

27.05.2010, 21:43

lgrizu

Auf diesen Beitrag antworten »

@ air
kein problem, kommt öfter vor Prost

Prost

27.05.2010, 21:46

kevin89

Auf diesen Beitrag antworten »

Zitat:

Original von lgrizu
ist nicht ganz richtig so weit.
beim induktionsschluss nicht einfach die zwei einsetzen:

nach IV ist $\begin{eqnarray*} a_n \leq 2 \Rightarrow \frac{1}{3-a_n} \leq 1 \Rightarrow 1+\frac{1}{3-a_n} \leq 2 \end{eqnarray*}$

Inwiefern bringt mich das jetzt weiter? Prinzipiell hab ich das doch schon im IA gezeigt...

Und ja, oben bei meiner IV fehlt das $\begin{eqnarray*} \leq \end{eqnarray*}$

Und inwiefern fange ich mit dem an was ich beweisen soll?
Ich rechne doch eigentlich mit dem n+1 Glied...

27.05.2010, 21:59

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von kevin89

Zitat:

Original von lgrizu
ist nicht ganz richtig so weit.
beim induktionsschluss nicht einfach die zwei einsetzen:

nach IV ist $\begin{eqnarray*} a_n \leq 2 \Rightarrow \frac{1}{3-a_n} \leq 1 \Rightarrow 1+\frac{1}{3-a_n} \leq 2 \end{eqnarray*}$

Inwiefern bringt mich das jetzt weiter? Prinzipiell hab ich das doch schon im IA gezeigt...

Und ja, oben bei meiner IV fehlt das $\begin{eqnarray*} \leq \end{eqnarray*}$

Und inwiefern fange ich mit dem an was ich beweisen soll?
Ich rechne doch eigentlich mit dem n+1 Glied...

ich rechne auch mit dem n+1-ten glied.

du hast ganz am anfang deines Induktionsschrittes geschrieben $\begin{eqnarray*} 2 \leq a_{n+1} \end{eqnarray*}$ , das willst du aber erst zeigen.

und dann kannst du doch nicht einfach die 2 in den induktionsschritt einsetzen, dann müsstest du erst zeigen, dass 2 der grenzwert der folge ist.
dazu müsste man dann zuerst zeigen, dass sie tatsächlich einen grenzwert besitzt, si kann auch durch 2 nach oben beschränkt sein, monoton fallen und keinen unteren grenzwert haben....(trifft bei dieser folge nicht zu..)
für deine folge gilt auch $\begin{eqnarray*} a_n < 3 \end{eqnarray*}$
setz mal die drei einfach ein, dann gibts nen problem......

27.05.2010, 22:13

kevin89

Auf diesen Beitrag antworten »

Ja klar, dass hab ich auch gegeben, dass soll quasi gezeigt werden das $\begin{eqnarray*} a_{n} \neq 3 \end{eqnarray*}$ wohldefiniert ist mit dem Hinweis: Zeigen sie $\begin{eqnarray*} a_{n} \leq 2 \end{eqnarray*}$ für alle n € |N

Hab meine Frage wohl etwas zu undeutlich formuliert.
Und in Teil b) soll die Monotonie erst gezeigt werden, also muss ich wohl ohne GW auskommen irgendwie.
In c) soll dann Konvergenz gegen einen GW gezeigt werden, was ja dann aus a) (da zeigt man doch BEschränktheit?) und b) folgt.
In d) wird der dann schließlich zu 2 berechnet, was ich schon erledigt habe...

27.05.2010, 22:17

lgrizu

Auf diesen Beitrag antworten »

aus beschränktheit nach oben (unten) und monoton steigend (fallend) folgt nach monotoniekriterium die konvergenz.

wie hat du denn einen grenzwert berechnet, ohne zu wissen, dass er existiert?

im allgemeinen sollte die reihenfolge doch sein:
man zeigt zuerst beschränktheit, dann monotonie und dann berechnet man den grenzwert.

27.05.2010, 22:22

kevin89

Auf diesen Beitrag antworten »

ja, klar.
ich dachte eben mit a) zeigt man beschränkung nach oben (oder etwa nicht?) und da ich dachte ich hätte das ordentlich gezeigt, hab ich monotonie gezeigt und somit konvergenz gefolgert und den ge bestimmt.

wie kann ich denn nun die a) (also das alle glieder kleiner gleich 2 sind) sauber zeigen ohne den gw zu kennen?

27.05.2010, 22:24

lgrizu

Auf diesen Beitrag antworten »

hab ich dir vor gemacht:

Zitat:

Original von lgrizu
nach IV ist $\begin{eqnarray*} a_n \leq 2 \Rightarrow \frac{1}{3-a_n} \leq 1 \Rightarrow 1+\frac{1}{3-a_n} \leq 2 \end{eqnarray*}$

edit: ja, man zeigt, dass die folge nach oben beschränkt ist.
und ja, man sollte ohne grenzwert auskommen, denn man benutzt induktion eigentlich standardmässig beim beweis der beschränktheit von folgen.

27.05.2010, 22:32

kevin89

Auf diesen Beitrag antworten »

aber wenn ich von der ersten ungleichung auf die zweite schließe, habe ich da dann nicht auch in gewissermaßen den gw benutzt?

oder zeigst du damit, dass es impliziert dass der bruch höchstens 1 wird auf grund der tatsache dass $\begin{eqnarray*} a_{n} \leq 2 \end{eqnarray*}$ (ist dass dann kein benutzen des gw? so hatte ich es nämlich auch prinzipiell in meiner rechung gemeint, da ja a_n nach voraussetzung höchstens 2 is)

27.05.2010, 22:38

lgrizu

Auf diesen Beitrag antworten »

ich benutze, dass $\begin{eqnarray*} a_n \leq 2 \end{eqnarray*}$ ist, keinen grenzwert.
wenn du das so gemeint hast, dann solltest du es auch so aufschreiben und nicht einfach irgendetwas einsetzen.

zu der kritik, die air noch gebracht hat, es gehört dazu, sich wirklich korrekt auszudrücken.

induktionen dieser art sind einfach, und es ist ärgerlich, wenn man punktabzüge bekommt weil man "geschlurt" hat.....

27.05.2010, 22:42

kevin89

Auf diesen Beitrag antworten »

also nutzt du in deiner ersten implikation einfach, dass auf grund von $\begin{eqnarray*} a_{n} \leq 2 \end{eqnarray*}$ der bruch maximal 1 oder eben kleiner wird und addierst auf beiden seiten 1 und zeigst dann, dass die entsprechende seite $\begin{eqnarray*} =a_{n+1} \end{eqnarray*}$ ist?

27.05.2010, 22:45

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von kevin89
......und zeigst dann, dass die entsprechende seite $\begin{eqnarray*} =a_{n+1} \end{eqnarray*}$ ist?

das zeige ich nicht, das nutze ich........

edit: ansonsten: genau so.....

27.05.2010, 22:50

kevin89

Auf diesen Beitrag antworten »

Zitat:

Original von lgrizu
hab ich dir vor gemacht:

[quote]Original von lgrizu
nach IV ist $\begin{eqnarray*} a_n \leq 2 \Rightarrow \frac{1}{3-a_n} \leq 1 \Rightarrow 1+\frac{1}{3-a_n} \leq 2 \end{eqnarray*}$

Kann man hinter die letzte Ungleichung jetzt nicht einfach

<=> $\begin{eqnarray*} a_{n+1} \leq 2 \end{eqnarray*}$ schreiben ?

Stehe scheinbar grad voll auf dem Schlauch...

27.05.2010, 22:53

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von kevin89

Zitat:

Original von lgrizu
hab ich dir vor gemacht:

[quote]Original von lgrizu
nach IV ist $\begin{eqnarray*} a_n \leq 2 \Rightarrow \frac{1}{3-a_n} \leq 1 \Rightarrow 1+\frac{1}{3-a_n} \leq 2 \end{eqnarray*}$

Kann man hinter die letzte Ungleichung jetzt nicht einfach

<=> $\begin{eqnarray*} a_{n+1} \leq 2 \end{eqnarray*}$ schreiben ?

Stehe scheinbar grad voll auf dem Schlauch...

kann man machen, denn $\begin{eqnarray*} a_{n+1}=1+\frac{1}{3-a_n} \end{eqnarray*}$ .

schreib die induktion doch jetzt noch mal sauber hin, im prinzip haben wir doch alles.....

27.05.2010, 22:56

kevin89

Auf diesen Beitrag antworten »

ok, dass meinte ich eben mit ersetzen.
ausdrücken sollte man sich können.
ich schreibs mal sauber auf papier und werds dann mal latexen Augenzwinkern

Augenzwinkern

27.05.2010, 23:04

lgrizu

Auf diesen Beitrag antworten »

okay, schau ich morgen mal drüber, muss jetzt ins bett, hab nen arzttermin morgen früh, bis morgen wirste das ja kaum brauchen, ist noch vorlesungsfrei (jedenfalls in niedersachsen)......

27.05.2010, 23:11

kevin89

Auf diesen Beitrag antworten »

Der Einfachheit halber hab ich das meistemal aus meiner ersten Ind. kopiert...

Also:
Gegeben ist:
$\begin{eqnarray*} a_{1}=1 , a_{n} = 1+ \frac{1}{3-a_{n-1} } \end{eqnarray*}$

Nun IA für n=2:

---> $\begin{eqnarray*} a_{2}=\frac {3}{2} \leq 2 \end{eqnarray*}$ ist korrekt.

IV: Sei $\begin{eqnarray*} a_{n} \leq 2 \end{eqnarray*}$ für ein n € |N bewiesen.

IS: n-->n+1
Behauptung: $\begin{eqnarray*} a_{n+1} \leq 2 \end{eqnarray*}$

Nach IV gilt:
$\begin{eqnarray*} a_{n} \leq 2 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow \frac{1}{3-a_{n} } \leq 1 \end{eqnarray*}$
<=> $\begin{eqnarray*} 1+ \frac{1}{3-a_{n} } \leq 2 \end{eqnarray*}$
<=> $\begin{eqnarray*} a_{n+1} \leq 2 \end{eqnarray*}$

Was zu zeigen war.

Anmerkungen? Augenzwinkern

Augenzwinkern

27.05.2010, 23:14

kevin89

Auf diesen Beitrag antworten »

Falss lgrizu nicht mehr da ist, wäre nett wenn vielleicht jemand anders schnell schauen könnte, brauchs dummerweise echt für morgen...

27.05.2010, 23:22

lgrizu

Auf diesen Beitrag antworten »

bin noch da...

soweit richtig....

27.05.2010, 23:24

kevin89

Auf diesen Beitrag antworten »

Super, hat ja dann doch noch geklappt smile

smile

Vielen Dank für die Hilfe.
Und das mit dem "Sei...." da legt unser Prof leider Wert drauf Big Laugh

Big Laugh

27.05.2010, 23:26

wisili

Auf diesen Beitrag antworten »

Für meinen Geschmack ist Folgendes zu kurz (aber richtig):

$\begin{eqnarray*} a_{n} \leq 2 \Rightarrow \frac{1}{3-a_{n} } \leq 1 \end{eqnarray*}$

Ausführlicher:

$\begin{eqnarray*} a_{n} \leq 2 \Rightarrow a_{n}-3 \leq 2-3 \Rightarrow 3-a_{n} \geq 1 \Rightarrow \frac{1}{3-a_{n} } \leq 1 \end{eqnarray*}$

27.05.2010, 23:27

lgrizu

Auf diesen Beitrag antworten »

habs auch editiert, weils überflüssig war das anzumerken.

also, gute nacht....

27.05.2010, 23:45

kevin89

Auf diesen Beitrag antworten »

Oh man...
hab gerade gemerkt das mein Monotoniebeweis hinkt.
Ich weiß, dass ich $\begin{eqnarray*} a_{n+1}-a_{n} \geq 0 \end{eqnarray*}$ zeigen muss (denkt euch das gleich weg, soll streng mon. sein) aber hab gerade gemerkt dass meine Endaussage $\begin{eqnarray*} a_{n}-a_{n-1} \geq 0 \end{eqnarray*}$ nicht viel mehr zeigt Hat dazu noch wer nen schnellen Tipp? Ansonsten hab ich Pech gehabt und bin selber Schuld es erst jetzt zu merken Big Laugh

Big Laugh

28.05.2010, 00:10

wisili

Auf diesen Beitrag antworten »

Setzt man für a_n die Rekursionsformel ein, so erhält man für die genannte Differenz einen Bruchterm mit a_n-1, der eindeutig positiv ist.

28.05.2010, 00:22

kevin89

Auf diesen Beitrag antworten »

naja wenn ich für $\begin{eqnarray*} a_{n} \end{eqnarray*}$ die Rekursionsformel einsetze erhalte ich ja
$\begin{eqnarray*} 1+ \frac{1}{3-a_{n-1} } - a_{n-1} \geq 0 \end{eqnarray*}$

Das der Bruch positiv ist, ist klar, aber warum ist die Differenz als ganzes größer als 0?

28.05.2010, 00:40

kevin89

Auf diesen Beitrag antworten »

Gibts niemand der mir schnell nochn Tipp geben kann?
Verstehe nicht was wisili meint, bzw komme damit auf nix brauchbare (für mich)

28.05.2010, 00:45

kevin89

Auf diesen Beitrag antworten »

Um es nochmal zu sagen, waren Fehler in den vorherigen Posts, es soll $\begin{eqnarray*} > \end{eqnarray*}$ gelten nicht $\begin{eqnarray*} \geq \end{eqnarray*}$

28.05.2010, 00:57

wisili

Auf diesen Beitrag antworten »

Zitat:

Original von kevin89
naja wenn ich für $\begin{eqnarray*} a_{n} \end{eqnarray*}$ die Rekursionsformel einsetze erhalte ich ja
$\begin{eqnarray*} 1+ \frac{1}{3-a_{n-1} } - a_{n-1} \geq 0 \end{eqnarray*}$

Das der Bruch positiv ist, ist klar, aber warum ist die Differenz als ganzes größer als 0?

Du sollst die linke Seite in einen Bruch umformen und den Zähler faktorisieren.

28.05.2010, 01:10

kevin89

Auf diesen Beitrag antworten »

Hab dafür jetzt

$\begin{eqnarray*} \frac{\left(a_{n-1} -2\right) ^{2} }{3-a_{n-1} } > 0 \end{eqnarray*}$ raus, aber a_n-1 kann doch auch nach dem bereits gezeigten auch den Wert 2 annehmen, also könnte der Bruch auch 0 werden und die Ungleichung wäre nicht mehr erfüllt, oder überseh ich was?...

28.05.2010, 01:22

wisili

Auf diesen Beitrag antworten »

Um 23.45 hast du noch die schwache Monotonie (mit Gleichheitszeichen) gemeint.
Wie dem auch sei, mit dem Startwert a1=2 hat man die konstante Folge 2, 2, 2, ...
Mit dem Startwert a1=1 hat man demzufolge (bei identischer Rekursionsformel) nie ein Glied der Grösse 2.

28.05.2010, 01:30

kevin89

Auf diesen Beitrag antworten »

Startwert a1=1 ist gegeben, aber wie begründe ich, dass 2 nie erreicht wird?
Die Konvergenz gegen 2 soll erst im folgenden Aufgabenteil gezeigt werden.

p.s.: das mit der echt-größer beziehung hatte ich einen post später erwähnt, vielleicht hast dus überlesen, macht ja nix

28.05.2010, 01:32

kevin89

Auf diesen Beitrag antworten »

Startwert a1=1 ist gegeben, aber wie begründe ich, dass 2 nie erreicht wird?
Die Konvergenz gegen 2 soll erst im folgenden Aufgabenteil gezeigt werden.
Wie zeig ich das sonst?

p.s.: das mit der echt-größer beziehung, also "starke" monotonie hatte ich einen post später erwähnt, vielleicht hast dus überlesen, macht ja nix, war ja schließlich mein fehler.
ansonsten wär deine argumentation auch nachvollziehbar Augenzwinkern

Augenzwinkern

28.05.2010, 01:35

wisili

Auf diesen Beitrag antworten »

Stimmt, habe jenen Hinweis überlesen.

Wenn ein Glied 2 ist, dann muss das nächstefolgende Glied aufgrund der Rekursionsformel wieder 2 sein.
Und das gilt auch rückwärts, da die Formel eindeutig nach a_n-1 aufgelöst werden kann.

12 nächste Seite »

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »