PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Mathe: Konvergenz rekursiver Folge


Marscel
2011-08-02, 02:45:39
Ich sitz seit knapp ner Stunde und raffs einfach nicht, schaut euch folgende Aufgabe bitte mal an:

http://666kb.com/i/bvpu6pke6tmpio98q.png

Der erste Abschnitt der Lösung, " ... b_n <= 1/2. This is obviously true for b_1."

Ehm, wissen wir das mit b_n nun schon irgendwo her (Schritt einfach nicht aufgeführt) oder will die Lösung uns das jetzt zeigen? Wenn letzteres, wie kann er dann hier schon mit b_1 als Induktionsbasis bestätigen? Ist doch schließlich auch kleiner als 1, Pi, e oder 42...

Im nächsten Schritt: Woher zum Henker kommt die (1/2)^2? Ist da irgendwo ein nicht erwähntes b_0 hergeholt? Nach dem Muster

b_n = 1/4 + (... + (1/4 + (1/4)^2)^2)^2 komm ich da nirgendwo auf ein Halb ohne mich damit auch gleich um die Konvergenz zu kümmern.

Entweder hab ich das Induktionsprinzip hier nicht erkennen oder ich hab einen Fehler in der Matrix.

Kann einer das näher ausführen?

Bis
2011-08-02, 04:18:10
du behauptest, dass b_n <= 1/2,
das stimmt zum einen für b_1 = 1/4 <= 1/2,
und zum anderen folgt eben wegen b_n <= 1/2 daraus auch:
b_n+1 = 1/4 + (b_n)^2 <= 1/4 + (1/2)^2 = 1/2,
was heisst, dass aus b_n <= 1/2 auch b_n+1 <= 1/2 folgt,
und damit aus b_1 <= 1/2 auch b_2 <= 1/2 auch b_3 <= 1/2 etc.
qed.

pest
2011-08-02, 06:19:44
Der erste Abschnitt der Lösung, " ... b_n <= 1/2. This is obviously true for b_1."

Ehm, wissen wir das mit b_n nun schon irgendwo her (Schritt einfach nicht aufgeführt) oder will die Lösung uns das jetzt zeigen? Wenn letzteres, wie kann er dann hier schon mit b_1 als Induktionsbasis bestätigen? Ist doch schließlich auch kleiner als 1, Pi, e oder 42...

Im nächsten Schritt: Woher zum Henker kommt die (1/2)^2? Ist da irgendwo ein nicht erwähntes b_0 hergeholt? Nach dem Muster


Ein Beweis über vollständige Induktion besteht aus 2 (eig. 3) Schritten.


Um zu beweisen, dass ein Satz für alle natürlichen Zahlen n ≥ m gilt, genügt es zu zeigen, dass er für n = m gilt und dass aus der Gültigkeit des Satzes für eine Zahl n ≥ m stets seine Gültigkeit auch für die folgende Zahl n+1 folgt


wir wollen zeigen das die Ungleichung für alle n>=1 gilt, also

Induktionsanfang: n=1: b_1=1/4 <= 1/2

daraus folgt die Induktionsvorraussetzung, nämlich das b_n <= 1/2 für ein n.

Induktionsschritt: jetzt müssen wir den Schritt n=>n+1 zeigen (je nachdem kann auch der schritt n-1 => n sinnvoll oder schöner sein)

b_(n+1) = 1/4 + (b_n)²
b_(n+1) <= 1/4 + (1/2)² (jetzt die Induktionsvorrausetzung einsetzen, das dürfen wir, da wir ja gezeigt haben, dass es für mind. ein n gilt)
b_(n+1) <= 1/2

Marscel
2011-08-02, 13:25:36
du behauptest, dass b_n <= 1/2

Aber wieso behaupte ich hier 1/2? Angenommen, da stünde keine Lösung, was hätte mich - außer vielleicht ein Gefühl, das ich hier nicht hatte - dort 1/2 wählen lassen sollen?

b_(n+1) <= 1/4 + (1/2)² (jetzt die Induktionsvorrausetzung einsetzen, das dürfen wir, da wir ja gezeigt haben, dass es für mind. ein n gilt)

Ach Mist, ich hab da immer was anderes eingesetzt. :usad:

Tiamat
2011-08-02, 13:47:26
Ich glaub Marscels Problem ist eher, wo denn die 1/2 herkommen.
Die gilt es ja erst mal herzuleiten, weil das keine feste Induktionsaufgabe ist, sondern Konvergenz oder Divergenz.

Das ist ganz einfach : Man muss die Folge vorteilhaft umformen.
Und zwar folgendermaßen, ich hab mir jeweils nach lim n->∞ vor jedem = Zeichen gespart. Das Ergebnis 1/4 ist der Grenzwert von b_n^2.
Folglich von b_n+1 1/4 + 1/4 = 1/2

Edit: Shit den Latex-Code kann man net gut erkennen. Kannst hier einfach einsetzen : http://www.codecogs.com/latex/eqneditor.php

b_n_+_1 = \frac{1}{4} + b_n^2 = \frac{1}{4} + \frac{1}{4^n} = \frac{4^n + 4}{4*4^n} = \frac{4^n(1 + \frac {4} {4^n})}{4^n(4 * \frac{1}{4^n})} = \frac{1}{4}


Ups: Ich hab da n Fehler drin, seh ich grad die Umformung 1/4^n reicht net, da war ich zu voreilig. Der Zähler ist doch kniffliger in dem Fall.

Gruß
Tiamat

Marscel
2011-08-02, 14:16:52
Die gilt es ja erst mal herzuleiten,

Der Schritt leuchtet ein - aber dann wäre die Induktion in der Lösung ja "nur" der Beweis, nicht die Herleitung, richtig?


b_n_+_1 = \frac{1}{4} + b_n^2 = \frac{1}{4} + \frac{1}{4^n} = \frac{4^n + 4}{4*4^n} = \frac{4^n(1 + \frac {4} {4^n})}{4^n(4 * \frac{1}{4^n})} = \frac{1}{4}


Ich glaube, du meinst es so: ;)

b_n_+_1 = \frac{1}{4} + b_n^2 = \frac{1}{4} + \frac{1}{4^n} = \frac{4^n + 4}{4*4^n} = \frac{4^n(1 + \frac {4} {4^n})}{4 * 4^n} = \frac{1+\frac{4}{4^n}}{4} = \frac{1}{4}

Tiamat
2011-08-02, 14:25:17
genau, das wäre nur der Beweis und der ließe sich auch mit 0.55 oder 0.6 durchführen ^^

Wie gesagt da steckt n Fehler drin, und zwar was den Zähler bei 1/4^n angeht. Allerdings sieht man , dass egal was im Zähler steht, für n -> ∞ genau dieser Bruch verschwindet.

Die Korrektur ist genau die gleiche, nur dass ich hervorheben wollte, wie man die n rauszieht.
Hoffe dir hilft das weiter. Ich hab im Grundstudium auch immer stundenlang vor solchem Zeug gehockt ^^

Bis
2011-08-02, 14:47:59
@tiamat
wieso sollte (b_n)^2 = 1/4^n sein?

@marscel
davon abgesehen, die 1/2 erhälst du aus der vorweggenommen annahme von konvergenz, dann gilt eben:
b_n = 1/4 + (b_n)^2

Tiamat
2011-08-02, 18:29:15
Ou, i´m sorry 4^n is sogar auch falsch.

Hier die korrigierte Fassung, X = Zählerwert, für den ich zeige, dass solange die Bedingung Zähler < Nenner erfüllt ist, später wegfällt und jetzt aus Faulheit durch ne Variable ersetzt wird.


b_n = \frac{1}{4} + \frac{x}{16^2^^^n^^^-^^^1} = \frac{16^2^^^n^^^-^^^1(1 + \frac{4x}{16^2^^^n^^^-^^^1})}{16^2^^^n^^^-^^^1 4} = \frac{1}{4}

das ganze gilt für n >= 1.

Nein die 1/2 kommen doch aus der Lösung, nicht aus der Aufgabe selbst.

Bis
2011-08-02, 20:52:50
@tiamat
mich interessiert mal, wie du auf deinen term kommst. ich täte behaupten, dass es für diese rekursion keine explizite darstellung gibt.

pest
2011-08-02, 21:18:34
Ich glaub Marscels Problem ist eher, wo denn die 1/2 herkommen.
Die gilt es ja erst mal herzuleiten, weil das keine feste Induktionsaufgabe ist, sondern Konvergenz oder Divergenz.


mach es nicht so kompliziert, eine beschränkte und monoton wachsende/fallende folge ist konvergent.

das die folge nach oben beschränkt ist, sieht man sofort, oder nach dem einzeiligen induktionsbeweis. man kann eine beliebige andere obere schranke wählen...


ich täte behaupten, dass es für diese rekursion keine explizite darstellung
gibt.


wie kommst du darauf?

Bis
2011-08-02, 21:41:31
ich sehe zumindest nicht gleich eine explizite darstellung. muss nit heissen, dass es nit doch eine gibt, ist auch nur eine behauptung von mir. aber tiamats term schaut mir sicher nicht nach der korrekten expliziten aus.

superdash
2011-08-02, 21:42:14
Imho ist das doch ganz typisch für die Mathematik, was wir hier als Beispiel sehen:

Viele Sätze sind nicht offensichtlich zu beweisen, auch wenn sie im Gefühl schon irgendwie logisch klingen und einleuchtend sind.

So ist doch fast immer der erste Schritt, sich zu überlegen, was man denn gerne beweisen würde und sich dann eine Beweisstrategie zu überlegen. Bei gorßen Sätzen gelingt das oft nur über viele Umwege und ist für Außenstehende dann kaum noch nachvollziebar.

Aber es bleibt dabei: der erste Schritt hat viel mit Gefühl und Spürsinn zu tun und der Induktionsbeweis treibt dies auf die Spitze und eignet sich besonders dann wenn das zu Grunde liegende Problem iwie isomorph zu den natürlichen Zahlen ist. Bei Folgen ist dies natürlich trivial offensichtlich.

Der Beweis ist dann erst die eigentliche Arbeit.

pest
2011-08-02, 21:48:14
viel wichtiger fände ich für dich zu klären wie sie den grenzwert der folge berechnen und warum das folgt.

superdash
2011-08-02, 22:04:21
Ich habe es mir nicht ins Detail angeschaut, aber ich denke folgendes:

- auf 1/2 kommt man durch scharfes hinsehen (oder geschicktes umformen, wenn mans nicht sieht)
- der Beweis funktioniert nicht für Zahlen kleiner 1/2, damit ist 1/2 ein guter Kandidat
- man kann dann sicher noch per widerspruch zeigen, dass zahlen kleiner 1/2 nicht der Grenzwert sein können
-> 1/2 ist grenzwert

Ob das die geschickteste Vorgehensweise ist, sei jetzt aber mal dahingestellt

pest
2011-08-02, 22:05:01
nein

superdash
2011-08-02, 22:08:16
Was meinst du genau?

pest
2011-08-02, 22:10:14
der grenzwert wird ja oben direkt berechnet. da der ts einen induktionsbeweis nicht so richtig verstanden hat, würde es mich interessieren ob er denn verstanden hat wie der grenzwert ermittelt wird. die rechnung geht analog wenn ich z.B. 10 als obere Schranke nehme, man muss die 1/2 nicht sehen.

superdash
2011-08-02, 22:15:22
ok.. alles klar.

Marscel
2011-08-02, 22:29:27
der grenzwert wird ja oben direkt berechnet. da der ts einen induktionsbeweis nicht so richtig verstanden hat, würde es mich interessieren ob er denn verstanden hat wie der grenzwert ermittelt wird. die rechnung geht analog wenn ich z.B. 10 als obere Schranke nehme, man muss die 1/2 nicht sehen.

Zum Ermitteln von Konvergenz und Grenzwerten hab ich ja ein halbes Dutzend Vorgehen, je nach Definition ist da eine am einfachsten. War bisher auch alles kein Problem.

Induktionsbeweise an sich eigentlich auch - naja, wenn da die Annahme bereits gegeben ist, ist das auch nicht schwierig.

Aber hier komm ich nicht weiter: Einmal ist in der Aufgabe ja gar keine Annahme gegeben, ich war mir nur sicher, dass die Folge gen >= 1/4 gehen muss. Konstruktiveres Vorgehen? Keine Ahnung :(

Die Lösung hat dann 1/2 als Behauptung eingeführt, das weiter unten dann auch als Grenzwert errechnet wird. Zusammenhang? Wenn ja, bin ich nicht draufgekommen.

pest
2011-08-02, 22:38:46
Die Lösung hat dann 1/2 als Behauptung eingeführt, das weiter unten dann auch als Grenzwert errechnet wird. Zusammenhang? Wenn ja, bin ich nicht draufgekommen.

1/2 ist nur eine obere schranke, das dies auch der grenzwert ist, naja, das ist ein glücklicher zufall ;)

da wir durch induktion gezeigt haben das die folge konvergiert (monoton steigend+beschränkt) und die folge die form a_(n+1)=g(a_n) besitzt,
wobei g eine diff'bare funktion bezeichnet, dann ist der grenzwert gleich einem fixpunkt der folge, also a=g(a). das setzen wir jetzt einfach in die Folgendefinition ein, also

a=1/4+a²

a²-a+1/4=0 => a=1/2 +/- Sqrt[1/4-1/4] => a=1/2

Marscel
2011-08-02, 22:59:53
*in before the board going down*

Jetzt dämmert mir was. 1/2 ist einfach ne glückliche Wahl und dank Induktion wissen, wir dass es glücklich bleibt, also irgendeine Form von Beschränkung hat.

Dann können wir ja monotonicity (deutscher Begriff? :ugly:) zeigen und dann damit auch Konvergenz.

Ouch, yessss, einen ganzen Tag geopfert.

Aber danke an alle!

Tiamat
2011-08-03, 02:08:11
@tiamat
mich interessiert mal, wie du auf deinen term kommst. ich täte behaupten, dass es für diese rekursion keine explizite darstellung gibt.

Ja, wir picken uns 3 Beispiele raus und zwar wir berechnen b(2), b(3) und b(4). b2 = 1/4 + (1/4)^2 , höchster Nenner 16
b(3) = 1/4 + (5/16)^2, höchster Nenner 256 = 16 * 16
b(4) = 1/4 + (89/256)^2, höchster Nenner 65536. = 16^4
b(5) = ... , höchster Nenner bla, = 16^8

D.h die Nenner beim b_n^2 Teil kann man als Folge 2^i ausdrücken. Jetzt musst man nur noch mit den Anfang bei 0 anfangen, weil
0 1 2 3, i
1 2 4 8, 2^i
Das kann schon mal verallgemeinert werden, deswegen 16^2^n-1

Knifflig wird´s bei Zähler : Allerdings bleibt der Wert des Zählers stets unterhalb des Wert des Nenners und fliegt bei der Betrachtung lim n->∞ sowieso raus, wie man beim letzten Post gesehen hat.

Es gibt bestimmt auch andere Varianten, da zu lösen, auf jeden Fall