rekursiv definierte Folge < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 13:22 Di 25.04.2017 | Autor: | Austinn |
Aufgabe | Die Folge [mm] x_{n} [/mm] sei rekursiv definiert durch [mm] x_{0}=0 [/mm] und [mm] x_{n+1}=\bruch{1}{2}x_{n}+1 [/mm] für [mm] n\in\IN.
[/mm]
a) Berechnen Sie [mm] x_{3}.
[/mm]
b) Sei n > 2. Geben Sie eine Formel für [mm] x_{n} [/mm] an, die lediglich von [mm] x_{n-2} [/mm] abhängt.
c) Zeigen Sie mittels vollständiger Induktion für alle 0 < [mm] n\in\IN [/mm] die Formel [mm] x_{n}=2-(\bruch{1}{2})^{n-1} [/mm] |
hallo,
a) und b) konnte ich leicht lösen. Mir bereitet die c) Schwierigkeiten, wobei ich hier überhaupt keine Idee habe.
a) [mm] x_{3}=\bruch{7}{4}
[/mm]
b) [mm] x_{n-2}=(\bruch{1}{2}x_{n}+1)-\bruch{7}{4}
[/mm]
Bei der c) habe ich leider keine Idee. Ich hoffe jemand kann helfen. Wie soll ich hier anfangen? Welche Formel und was soll ich hier genau zeigen?
Danke!
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:33 Di 25.04.2017 | Autor: | fred97 |
> Die Folge [mm]x_{n}[/mm] sei rekursiv definiert durch [mm]x_{0}=0[/mm] und
> [mm]x_{n+1}=\bruch{1}{2}x_{n}+1[/mm] für [mm]n\in\IN.[/mm]
> a) Berechnen Sie [mm]x_{3}.[/mm]
> b) Sei n > 2. Geben Sie eine Formel für [mm]x_{n}[/mm] an, die
> lediglich von [mm]x_{n-2}[/mm] abhängt.
> c) Zeigen Sie mittels vollständiger Induktion für alle 0
> < [mm]n\in\IN[/mm] die Formel [mm]x_{n}=2-(\bruch{1}{2})^{n-1}[/mm]
> hallo,
> a) und b) konnte ich leicht lösen. Mir bereitet die c)
> Schwierigkeiten, wobei ich hier überhaupt keine Idee
> habe.
>
> a) [mm]x_{3}=\bruch{7}{4}[/mm]
Das stimmt.
> b) [mm]x_{n-2}=(\bruch{1}{2}x_{n}+1)-\bruch{7}{4}[/mm]
Wie kommst Du denn darauf ???? Mach mal vor !
>
> Bei der c) habe ich leider keine Idee. Ich hoffe jemand
> kann helfen. Wie soll ich hier anfangen? Welche Formel und
> was soll ich hier genau zeigen?
Du sollst zeigen, dass gilt:
$ [mm] x_{n}=2-(\bruch{1}{2})^{n-1} [/mm] $ für jedes $n [mm] \in \IN$.
[/mm]
Beweisen sollst Du das mit Induktion.
>
> Danke!
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 14:02 Di 25.04.2017 | Autor: | Austinn |
> Wie kommst Du denn darauf ???? Mach mal vor !
[mm] x_{n-2}=x_{n+1}-x_{3}, [/mm] also vom Ergebnis von [mm] x_{n+1} [/mm] einfach immer [mm] x_{3} [/mm] abziehen.
Ich hoffe es ist richtig. Die Ergebnisse mit n > 2 in [mm] x_{n-2} [/mm] stimmen jedenfalls.
Die c) verstehe ich leider nicht. Kannst du mir eventuell an der c) zeigen, wie man an so einer Aufgabe rangehen kann?
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 14:14 Di 25.04.2017 | Autor: | fred97 |
> > Wie kommst Du denn darauf ???? Mach mal vor !
> [mm]x_{n-2}=x_{n+1}-x_{3},[/mm]
Wie kommst Du darauf ??? Das ist abenteuerlich ! Begründung ?
> also vom Ergebnis von [mm]x_{n+1}[/mm]
> einfach immer [mm]x_{3}[/mm] abziehen.
> Ich hoffe es ist richtig. Die Ergebnisse mit n > 2 in
> [mm]x_{n-2}[/mm] stimmen jedenfalls.
>
> Die c) verstehe ich leider nicht. Kannst du mir eventuell
> an der c) zeigen, wie man an so einer Aufgabe rangehen
> kann?
Ist Dir klar, wie das Beweisverfahren "Vollständige Induktion " funktioniert ?
>
>
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 14:18 Di 25.04.2017 | Autor: | Austinn |
> Wie kommst Du darauf ??? Das ist abenteuerlich ! Begründung ?
Ich nehme an es ist falsch :D? Ich weiss nicht wie Dir das anders erklären könnte. Auch hier bräuchte ich dann hilfe :/
> Ist Dir klar, wie das Beweisverfahren "Vollständige Induktion " funktioniert ?
Ja, aber ich habe das noch nie an Folgen gesehen.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 14:25 Di 25.04.2017 | Autor: | fred97 |
> > Wie kommst Du darauf ??? Das ist abenteuerlich !
> Begründung ?
> Ich nehme an es ist falsch :D?
Möglich .
> Ich weiss nicht wie Dir das
> anders erklären könnte.
Erklärt hast Du gar nix. Du hast nur hingeschrirben:
$ [mm] x_{n-2}=(\bruch{1}{2}x_{n}+1)-\bruch{7}{4} [/mm] $.
Dann hab ich Dich nach einer Begründung für diese Formel gefragt. Die hast Du nicht gliefert ! Also nochmal: wie bist Du auf diese Formel gekommen ?.
> Auch hier bräuchte ich dann
> hilfe :/
>
> > Ist Dir klar, wie das Beweisverfahren "Vollständige
> Induktion " funktioniert ?
> Ja, aber ich habe das noch nie an Folgen gesehen.
Flexibilität ?
Du sollst zeigen
(*) $ [mm] x_{n}=2-(\bruch{1}{2})^{n-1} [/mm] $
für jedes n [mm] \in \IN.
[/mm]
Zunächst zeigst Du, dass (*) für n=1 stimmt (Induktionsanfang).
Dann nimmst Du an, dass (*) für ein gewisses n richtig ist (Induktionsvoraussetzung). Damit zeigst Du dann, dass (*) auch für n+1 stimmt, dass also
$ [mm] x_{n+1}=2-(\bruch{1}{2})^{n} [/mm] $
ist.
Dann leg mal los !
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 18:45 Di 25.04.2017 | Autor: | Austinn |
Ja das war völliger quatsch, was ich in der b gemacht habe :D.
Ich mache deshalb jetzt die c).
IS:
[mm] x_{n+1}=2-(\bruch{1}{2})^{(n+1)-1}=2-\bruch{(\bruch{1}{2})^{n+1}}{\bruch{1}{2}}=2-(\bruch{1}{2})^{n+1}*2=2-(\bruch{1}{2})^{n}*\bruch{1}{2}*2=2-(\bruch{1}{2})^{n}*1=2-(\bruch{1}{2})^{n}
[/mm]
Ich hoffe es stimmt. Bei der b) brauche ich jetzt Hilfe. :/
|
|
|
|
|
Hallo,
> Ich mache deshalb jetzt die c).
>
> IS:
>
> [mm]x_{n+1}=2-(\bruch{1}{2})^{(n+1)-1}=\bruch{(\bruch{1}{2})^{n+1}}{\bruch{1}{2}}=2-(\bruch{1}{2})^{n+1}*2=2-(\bruch{1}{2})^{n}*\bruch{1}{2}*2=2-(\bruch{1}{2})^{n}*1=2-(\bruch{1}{2})^{n}[/mm]
> Ich hoffe es stimmt.
Stimmen tut es bis auf das, was du vergessen hast einzutippen. Beispielsweis nach der zweiten Gleichheit die '2-'. Und den Induktionsanfang, ohne den das ganze keinen Pfifferling wert ist.
Und Effizienz sieht anders aus:
IA:
[mm]x_0=2-\left( \frac{1}{2}\right)^{0-1}=2-2=0[/mm]
IS:
[mm]x_{n+1}=2-\left(\frac{1}{2}\right)^{(n+1)-1}=2-\left(\frac{1}{2}\right)^n[/mm]
Fertig.
> Bei der b) brauche ich jetzt Hilfe.
Ersetze in deiner Rekursionvorschrift zunächst [mm] x_n [/mm] durch [mm] x_{n-1}, [/mm] vereinfache und ersetze dann [mm] x_{n-1} [/mm] durch [mm] x_{n-2} [/mm] und vereinfache erneut.
Und wenn du das nächste mal schreibst '...brauche ich jetzt Hilfe' dann wäre es eine konstruktive Sache (und damit in deinem Sinne!), wenn du präzisieren könntest, was genau dein Verständnisproblem ist.
Gruß, Diophant
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 19:49 Di 25.04.2017 | Autor: | Austinn |
Hallo,
> Und wenn du das nächste mal schreibst '...brauche ich jetzt Hilfe' dann wäre es eine konstruktive Sache (und damit in deinem Sinne!), wenn du präzisieren könntest, was genau dein Verständnisproblem ist.
Mein Verständnisproblem ist, wie ich in "der Rekursionvorschrift zunächst [mm] x_n [/mm] durch [mm] x_{n-1} [/mm] ersetze, vereinfache und dann [mm] x_{n-1}durch x_{n-2} [/mm] und erneut vereinfache."
Bzw. was ist [mm] x_{n-1} [/mm] und wie und wo setze ich es ein?
|
|
|
|
|
Hallo,
[mm] x_{n-1}=\frac{1}{2}x_{n-2}+1
[/mm]
Jetzt klarer?
Gruß, Diophant
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 21:45 Di 25.04.2017 | Autor: | X3nion |
Hallo Austinn,
nochmals zur vollständigen Induktion:
Sei eine Folge [mm] (x_n) [/mm] rekursiv definiert durch $ [mm] x_{0}=0 [/mm] $ und $ [mm] x_{n+1}=\bruch{1}{2}x_{n}+1 [/mm] $ für $ [mm] n\in\IN. [/mm] $
Zu zeigen ist mittels vollständiger Induktion für alle n [mm] \ge [/mm] 0, n [mm] \in \IN [/mm] die Formel:
[mm] x_{n} [/mm] = 2 - [mm] (\frac{1}{2})^{n-1}.
[/mm]
(Hier vermute ich einen Tippfehler von dir, denn die Formel ist auch für n=0 wahr.
Es soll also die Formel [mm] x_{n} [/mm] = 2 - [mm] (\frac{1}{2})^{n-1} [/mm] (eine explizite Darstellung der gegebenen Folge) mithilfe der rekursiven Folge gezeigt werden.
Induktionsanfang: n=0:
Es ist [mm] x_{0} [/mm] = 2 - [mm] (\frac{1}{2})^{0-1} [/mm] = 2 - [mm] (\frac{1}{2})^{-1} [/mm] = 2 - [mm] (2^{-1})^{-1} [/mm] = 2 - [mm] 2^{(-1)*(-1)} [/mm] = 2 - [mm] 2^{1} [/mm] = 2-2 = 0
In der rekursiven Folge ist: [mm] x_{0} [/mm] = 0 gemäß Startwert der rekursiven Folge.
Folglich ist der Induktionsanfang wahr, da für beide [mm] x_{0} [/mm] = 0 gilt.
Induktionsvoraussetzung:
[mm] x_{n} [/mm] = 2 - [mm] (\frac{1}{2})^{n-1} [/mm] gelte für ein n [mm] \in \IN, [/mm] n [mm] \ge [/mm] 0
Induktionsschritt: n -> n+1
Zu zeigen ist also die Gültigkeit der Formel [mm] x_{n+1} [/mm] = 2 - [mm] (\frac{1}{2})^{(n+1)-1} [/mm] = 2 - [mm] (\frac{1}{2})^{n} [/mm] unter Annahme der Gültigkeit der Induktionsvoraussetzung
Nun schreiten wir zur Tat:
Es ist gemäß rekursiver Definition der Folge:
[mm] x_{n+1} [/mm] = [mm] \frac{1}{2}x_{n} [/mm] + 1 (*)
Setze die Induktionsvoraussetzung [mm] x_{n} [/mm] = 2 - [mm] (\frac{1}{2})^{n-1} [/mm] in (*) ein, daraus folgt dann:
[mm] x_{n+1} [/mm] = [mm] \frac{1}{2}x_{n} [/mm] + 1 = [mm] \frac{1}{2}[2 [/mm] - [mm] (\frac{1}{2})^{n-1})] [/mm] + 1 = [mm] \frac{1}{2}*2 [/mm] - [mm] \frac{1}{2} [/mm] * [mm] (\frac{1}{2})^{n-1} [/mm] + 1 = 1 - [mm] (\frac{1}{2})^{n} [/mm] + 1 = 2 - [mm] (\frac{1}{2})^{n} [/mm]
was zu zeigen war.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 22:06 Di 25.04.2017 | Autor: | X3nion |
Zur Teilaufgabe b)
Schauen wir uns die Aufgabenstellung an:
"Sei n > 2. Geben Sie eine Formel für $ [mm] x_{n} [/mm] $ an, die lediglich von $ [mm] x_{n-2} [/mm] $ abhängt. "
Hier bin ich wieder der Meinung dass du dich vertippt hast und es n [mm] \ge [/mm] 2 heißen soll.
Wir haben die rekursive Folge $ [mm] x_{n} [/mm] $ gegeben durch $ [mm] x_{0}=0 [/mm] $ und $ [mm] x_{n+1}=\bruch{1}{2}x_{n}+1 [/mm] $ für $ [mm] n\in\IN. [/mm] $
Also: hat man [mm] x_{0}, [/mm] so kann man [mm] x_{0+1} [/mm] = [mm] x_{1} [/mm] berechnen,
hat man [mm] x_{1}, [/mm] so kann man [mm] x_{1+1} [/mm] = [mm] x_{2} [/mm] berechnen,
hat man [mm] x_{2} [/mm] gegeben, so berechnet man [mm] x_{2+1} [/mm] = [mm] x_{3} [/mm] usw..
Allgemein: man berechnet aus dem n-ten Folgenglied den (n+1)-ten Nachfolger
Hier soll man (für n > 2) eine Rekursionsformel für [mm] x_{n} [/mm] angeben, die nur von [mm] x_{n-2}, [/mm] also vom Vorvorgänger abhängt.
Nun denn: es ist
[mm] x_{n+1} [/mm] = [mm] \frac{1}{2}x_{n} [/mm] + 1, für n [mm] \ge [/mm] 0
bzw. durch Indexverschiebung ergibt sich:
(*) [mm] x_{n} [/mm] = [mm] \frac{1}{2}x_{n-1} [/mm] + 1, für n [mm] \ge [/mm] 1
[mm] x_{n-1} [/mm] = [mm] \frac{1}{2}x_{n-2} [/mm] + 1, für n [mm] \ge [/mm] 2
Hierbei sollte der klar sein, dass es sich um äquivalente Darstellungen der rekursiven Folge handelt.
Nun die Preisfrage an dich: Was müssen wir tun, damit wir [mm] x_{n} [/mm] in Abhängigkeit von [mm] x_{n-2} [/mm] erhalten?
Viele Grüße,
X3nion
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 23:14 Di 25.04.2017 | Autor: | Austinn |
[mm] x_{n-2}=\frac{1}{2}x_{n-3}+1 [/mm] ?
Aber wieso darf ich das machen? Und wäre jetzt das schon die Lösung?
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 23:42 Di 25.04.2017 | Autor: | X3nion |
Hallo Austinn,
> [mm] x_{n-2}=\frac{1}{2}x_{n-3}+1?
[/mm]
> Aber wieso darf ich das machen? Und wäre jetzt das schon die Lösung?
Du hast jetzt [mm] x_{n-2} [/mm] in Abhängigkeit von [mm] x_{n-3} [/mm] stehen, aber es sollte [mm] x_{n} [/mm] in Abhängigkeit von [mm] x_{n-2} [/mm] vorkommen, und zwar nur von [mm] x_{n-2} [/mm] !
Ich zitiere aus meinen Beitrag:
> Nun denn: es ist
> [mm] x_{n+1} [/mm] = [mm] \frac{1}{2}x_{n} [/mm] + 1, für n [mm] \ge [/mm] 0
> (*) [mm] x_{n} [/mm] = [mm] \frac{1}{2}x_{n-1} [/mm] + 1, für n [mm] \ge [/mm] 1
> [mm] x_{n-1} [/mm] = [mm] \frac{1}{2}x_{n-2} [/mm] + 1, für n [mm] \ge [/mm] 2
Den Indexschift darfst du machen, weil dann dasselbe dasteht.
Überzeuge dich von der Äquivalenz von
1) [mm] x_{n+1} [/mm] = [mm] \frac{1}{2}x_{n} [/mm] + 1, für n [mm] \ge [/mm] 0 und
2) (*) [mm] x_{n} [/mm] = [mm] \frac{1}{2}x_{n-1} [/mm] + 1, für n [mm] \ge [/mm] 1
1) Es ist [mm] x_{0} [/mm] = 0 der Startwert.
=> für n = 0: [mm] x_{0+1} [/mm] = [mm] x_{1} [/mm] = [mm] \frac{1}{2}x_{0} [/mm] + 1 = 1
=> für n = 1: [mm] x_{1+1} [/mm] = [mm] x_{2} [/mm] = [mm] \frac{1}{2}x_{1} [/mm] + 1 = [mm] \frac{1}{2} [/mm] + 1 = [mm] \frac{3}{2}
[/mm]
=> ...
2) Es ist wiederum [mm] x_{0} [/mm] = 0 der Startwert
=> für n = 1: [mm] x_{1} [/mm] = [mm] \frac{1}{2}x_{1-1} [/mm] + 1 = [mm] \frac{1}{2}x_{0} [/mm] + 1 = 1
=> für n = 2: [mm] x_{2} [/mm] = [mm] \frac{1}{2}x_{2-1} [/mm] + 1 = [mm] \frac{1}{2}x_{1} [/mm] + 1 = [mm] \frac{1}{2} [/mm] * 1 + 1 = [mm] \frac{3}{2}
[/mm]
=> ...
Und analog ist jeder Indexshift zulässig, solange die Formel für n [mm] \ge [/mm] 0 gilt.
Also [mm] x_{n+2} [/mm] = [mm] \frac{1}{2}x_{n+1} [/mm] + 1 wäre nicht möglich, will man die gesamte Formel darstellen für n [mm] \in \IN. [/mm] Denn hier ist für n = -1: [mm] x_{-1+2} [/mm] = [mm] x_{1} [/mm] = [mm] \frac{1}{2}x_{-1+1} [/mm] + 1 = [mm] \frac{1}{2}x_{0} [/mm] + 1 = 1, aber -1 [mm] \not\in \IN
[/mm]
Jetzt noch ein Versuch, du bist kurz davor und musst nur korrekt einsetzen!
> [mm] x_{n+1} [/mm] = [mm] \frac{1}{2}x_{n} [/mm] + 1, für n [mm] \ge [/mm] 0
> (*) [mm] x_{n} [/mm] = [mm] \frac{1}{2}x_{n-1} [/mm] + 1, für n [mm] \ge [/mm] 1
> [mm] x_{n-1} [/mm] = [mm] \frac{1}{2}x_{n-2} [/mm] + 1, für n [mm] \ge [/mm] 2
Es ist also [mm] x_{n} [/mm] = [mm] \frac{1}{2}x_{n-1} [/mm] + 1, für n [mm] \ge [/mm] 1
Hier steht auf der linken Seite aber [mm] x_{n-1}.
[/mm]
Was musst du also tun, damit [mm] x_{n} [/mm] nur in Abhängigkeit von [mm] x_{n-2} [/mm] dasteht?
Viele Grüße,
X3nion
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 12:39 Mi 26.04.2017 | Autor: | Austinn |
[mm] x_{n}=\bruch{1}{4}x_{n-2}+\bruch{3}{2}?
[/mm]
|
|
|
|