Induktion - Xn < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei [mm] x_{0} [/mm] = 0 und [mm] x_{1} [/mm] = 1
Für n [mm] \ge [/mm] 1 werde rekursiv definiert:
[mm] x_{n+1} [/mm] = [mm] 4x_{n} [/mm] - [mm] 3x_{n-1}
[/mm]
Zeigen Sie, dass [mm] x_{n} [/mm] = [mm] \bruch{(3^{n}-1)}{2} \forall [/mm] n [mm] \in \IN [/mm] |
Mein Ansatz:
[mm] x_{n+1} [/mm] = [mm] 4x_{n} [/mm] - [mm] 3x_{n-1}
[/mm]
[mm] \gdw x_{n} [/mm] = [mm] \bruch {x_{n+1} + 3x_{n-1}}{4}
[/mm]
Und jetzt mit vollständiger Induktion zeigen, dass:
[mm] \bruch {x_{n+1} + 3x_{n-1}}{4} [/mm] = [mm] \bruch{(3^{n}-1)}{2} [/mm] ist.
IA: n = 1
[mm] \bruch{x_2 + 3x_0}{4} [/mm] = [mm] \bruch{(3-1)}{2}
[/mm]
[mm] \gdw x_2 [/mm] + [mm] 3x_0 [/mm] = 4
[mm] \gdw 4x_{1} [/mm] - [mm] 3x_{0} [/mm] + [mm] 3x_0 [/mm] = 4
[mm] \gdw [/mm] 4 - 3*0 +3*0 = 4
[mm] \gdw [/mm] 4 = 4
IV: Die Behauptung gilt bis n
IS: n -> n+1 :
[mm] \bruch {x_{n+2} + 3x_{n}}{4} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch {4x_{n+1} - 3x_{n} + 3x_{n}}{4} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw x_{n+1} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2} [/mm] q.e.d.
Könnt ihr dem so zustimmen?
|
|
| |
|
Hallo Andreas,
> Es sei [mm]x_{0}[/mm] = 0 und [mm]x_{1}[/mm] = 1
> Für n [mm]\ge[/mm] 1 werde rekursiv definiert:
>
> [mm]x_{n+1}[/mm] = [mm]4x_{n}[/mm] - [mm]3x_{n-1}[/mm]
>
> Zeigen Sie, dass [mm]x_{n}[/mm] = [mm]\bruch{(3^{n}-1)}{2} \forall[/mm] n
> [mm]\in \IN[/mm]
> Mein Ansatz:
>
> [mm]x_{n+1}[/mm] = [mm]4x_{n}[/mm] - [mm]3x_{n-1}[/mm]
> [mm]\gdw x_{n}[/mm] = [mm]\bruch {x_{n+1} + 3x_{n-1}}{4}[/mm]
>
> Und jetzt mit vollständiger Induktion zeigen, dass:
>
> [mm]\bruch {x_{n+1} + 3x_{n-1}}{4}[/mm] = [mm]\bruch{(3^{n}-1)}{2}[/mm] ist.
>
> IA: n = 1
> [mm]\bruch{x_2 + 3x_0}{4}[/mm] = [mm]\bruch{(3-1)}{2}[/mm]
> [mm]\gdw x_2[/mm] + [mm]3x_0[/mm] = 4
> [mm]\gdw 4x_{1}[/mm] - [mm]3x_{0}[/mm] + [mm]3x_0[/mm] = 4
> [mm]\gdw[/mm] 4 - 3*0 +3*0 = 4
> [mm]\gdw[/mm] 4 = 4 ![[ok]](/images/smileys/ok.gif "[ok]")
>
> IV: Die Behauptung gilt bis n
>
> IS: n -> n+1 :
>
> [mm]\bruch {x_{n+2} + 3x_{n}}{4}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch {4x_{n+1} - 3x_{n} + 3x_{n}}{4}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw x_{n+1}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm] q.e.d.
Nee, was hast du hier gezeigt?
Nichts, oder? Zu Beginn und am Ende steht dasselbe und dazwischen Äquivalenzpfeile ...
Du musst ja auch irgendwo die Induktionsvoraussetzung einbauen ...
Besser im Induktionsschritt so:
IV: Sei [mm] $n\in\IN$ [/mm] beliebig, aber fest und gelte für alle [mm] $k\le [/mm] n$: [mm] $x_k=\frac{3^k-1}{2}$
[/mm]
Dann ist im Induktionsschritt zu zeigen, dass [mm] $x_{n+1}=\frac{3^{n+1}-1}{2}$ [/mm] ist.
Dazu benutze die Definition von [mm] $x_{n+1}$
[/mm]
[mm] $x_{n+1}=4x_n-3x_{n-1}$
[/mm]
Nun kannst du auf [mm] $x_n$ [/mm] und [mm] $x_{n-1}$ [/mm] jeweils die Induktionsvoraussetzung anwenden.
Mache das mal und rechne den Spaß dann schön zusammen, so dass am Ende [mm] $\frac{3^{n+1}-1}{2}$ [/mm] rauskommt
>
>
> Könnt ihr dem so zustimmen?
Dem Induktionsschritt nicht
Gruß
schachuzipus
>
|
|
|
| |
|
Dann noch ein Versuch. Danke schachuzipus für deine schnellen und tollen Antworten.
Die umgekehrte Dreiecksungleichung werde ich etwas später behandeln, da ich eine Seite gefunden habe, wo eine Uni die Übungsblätter des Sommersemesters 09/10 veröffentlicht hat.
Die Ungleichung kommt sogar auch drin vor, aber erst in der 3en Woche.
Momentan bin ich noch am ersten^^
Das mit [mm] x_k [/mm] verstehe ich noch nicht ganz =/, ich hab es mal so probiert:
[mm] x_{n+1} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw 4x_n [/mm] - [mm] 3x_{n-1} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{4(3^{n}-1)-3(3^{n-1}-1)}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{4*3^{n}-3*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{12*3^{n-1}-3*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{9*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{3^{n+1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
So richtig?
So hätte ich es jedenfalls in der Schule aufgeschrieben.
Mir wurde jedoch oft genug gesagt, dass man da an der Uni etwas ausführlicher vorgehen muss.
Hier ein Versuch:
[mm] x_{n+1} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2} [/mm]
[mm] \gdw 4x_n [/mm] - [mm] 3x_{n-1} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2} [/mm]
[mm] \gdw \bruch{4(3^{n}-1)}{2} [/mm] - [mm] \bruch{3(3^{n-1}-1)}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{4(3^{n}-1)-3(3^{n-1}-1)}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Distributivgesetz:
[mm] \gdw \bruch{4*3^{n}-4*1-(3*3^{n-1}-3*1)}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Distributivgesetz:
[mm] \gdw \bruch{4*3^{n}-4*1-3*3^{n-1}+3*1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Kommutativgesetz
[mm] \gdw \bruch{4*3^{n}-3*3^{n-1}-4*1+3*1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] 3^n [/mm] = [mm] 3^{n-1} [/mm] * 3
[mm] \gdw \bruch{4*(3^{n-1}*3)-3*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Kommutativgesetz
[mm] \gdw \bruch{4*(3*3^{n-1})-3*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Assoziativgesetz
[mm] \gdw \bruch{(4*3)*3^{n-1}-3*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{12*3^{n-1}-3*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Distributivgesetz
[mm] \gdw \bruch{(12-3)*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{9*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{3^2*3^{n-1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{3^{2+(n-1)}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
[mm] \gdw \bruch{3^{n+1}-1}{2} [/mm] = [mm] \bruch{(3^{n+1}-1)}{2}
[/mm]
Ist das so zu viel oder noch zu wenig?
Danke im Voraus.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:13 Di 05.10.2010 | | Autor: | fred97 |
> Dann noch ein Versuch. Danke schachuzipus für deine
> schnellen und tollen Antworten.
> Die umgekehrte Dreiecksungleichung werde ich etwas später
> behandeln, da ich eine Seite gefunden habe, wo eine Uni die
> Übungsblätter des Sommersemesters 09/10 veröffentlicht
> hat.
> Die Ungleichung kommt sogar auch drin vor, aber erst in
> der 3en Woche.
> Momentan bin ich noch am ersten^^
>
>
> Das mit [mm]x_k[/mm] verstehe ich noch nicht ganz =/, ich hab es mal
> so probiert:
>
> [mm]x_{n+1}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw 4x_n[/mm] - [mm]3x_{n-1}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch{4(3^{n}-1)-3(3^{n-1}-1)}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch{4*3^{n}-3*3^{n-1}-1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch{12*3^{n-1}-3*3^{n-1}-1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch{9*3^{n-1}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch{3^{n+1}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> So richtig?
>
Ja, aber nicht schön.
> So hätte ich es jedenfalls in der Schule aufgeschrieben.
> Mir wurde jedoch oft genug gesagt, dass man da an der Uni
> etwas ausführlicher vorgehen muss.
> Hier ein Versuch:
>
> [mm]x_{n+1}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw 4x_n[/mm] - [mm]3x_{n-1}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
> [mm]\gdw \bruch{4(3^{n}-1)}{2}[/mm] - [mm]\bruch{3(3^{n-1}-1)}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> [mm]\gdw \bruch{4(3^{n}-1)-3(3^{n-1}-1)}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Distributivgesetz:
>
> [mm]\gdw \bruch{4*3^{n}-4*1-(3*3^{n-1}-3*1)}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Distributivgesetz:
>
> [mm]\gdw \bruch{4*3^{n}-4*1-3*3^{n-1}+3*1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Kommutativgesetz
>
> [mm]\gdw \bruch{4*3^{n}-3*3^{n-1}-4*1+3*1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> [mm]3^n[/mm] = [mm]3^{n-1}[/mm] * 3
>
> [mm]\gdw \bruch{4*(3^{n-1}*3)-3*3^{n-1}-1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Kommutativgesetz
>
> [mm]\gdw \bruch{4*(3*3^{n-1})-3*3^{n-1}-1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Assoziativgesetz
>
> [mm]\gdw \bruch{(4*3)*3^{n-1}-3*3^{n-1}-1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> [mm]\gdw \bruch{12*3^{n-1}-3*3^{n-1}-1}{2}[/mm] =
> [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Distributivgesetz
>
>
> [mm]\gdw \bruch{(12-3)*3^{n-1}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
>
> [mm]\gdw \bruch{9*3^{n-1}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> [mm]\gdw \bruch{3^2*3^{n-1}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
>
> [mm]\gdw \bruch{3^{2+(n-1)}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
>
> [mm]\gdw \bruch{3^{n+1}-1}{2}[/mm] = [mm]\bruch{(3^{n+1}-1)}{2}[/mm]
>
> Ist das so zu viel oder noch zu wenig?
Zu viel
Kurz , knapp und korrekt geht das so:
Mit der IV bekommt man:
[mm] $x_{n+1}=\bruch{4(3^n-1)}{2}-\bruch{3(3^{n-1}-1)}{2}= \bruch{4*3^n-4-3^n+3}{2}= \bruch{3^{n+1}-1}{2}$
[/mm]
FRED
>
> Danke im Voraus.
|
|
|
|
