Rekursive Definition < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:46 So 25.10.2009 | | Autor: | Doemmi |
| 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 bitte, dass dann [mm] x_{n} [/mm] = [mm] \bruch{3^{n}-1}{2} [/mm] für alle n [mm] \in \IN [/mm] ist. |
Ich dachte mir, ich versuche das mit vollständiger Induktion:
Induktionsanfang: Sei n = 1
[mm] \Rightarrow x_{1} [/mm] = [mm] \bruch{3 - 1}{2} [/mm] = 1
Für n = 1 gilt die Behauptung
Induktionsvoraussetzung: Die Behauptung gelte für ein beliebiges, aber festes n.
Induktionsschritt: n [mm] \to [/mm] n + 1
[mm] \Rightarrow x_{n+1} [/mm] = [mm] \bruch{3^{n+1} - 1}{2}
[/mm]
nach Definition gilt: [mm] x_{n+1} [/mm] = [mm] 4x_{n} [/mm] - [mm] 3x_{n-1}
[/mm]
[mm] \Rightarrow \bruch{3^{n+1} - 1}{2} [/mm] = [mm] 4x_{n} [/mm] - [mm] 3x_{n-1}
[/mm]
So, weiter komme ich irgendwie nicht...
|
|
| |
|
Hallo!
> 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 bitte, dass dann [mm]x_{n}[/mm] = [mm]\bruch{3^{n}-1}{2}[/mm] für
> alle n [mm]\in \IN[/mm] ist.
Find' ich ja nett, dass sie bei euch in den Aufgabenstellungen "bitte" verwenden 
> Ich dachte mir, ich versuche das mit vollständiger
> Induktion:
Gute Idee ! ![[ok]](/images/smileys/ok.gif "[ok]")
> Induktionsanfang: Sei n = 1
>
> [mm]\Rightarrow x_{1}[/mm] = [mm]\bruch{3 - 1}{2}[/mm] = 1
>
> Für n = 1 gilt die Behauptung
>
>
> Induktionsvoraussetzung: Die Behauptung gelte für ein
> beliebiges, aber festes n.
Wichtig: Für den Beweis brauchen wir auch, dass die Aussage für n-1 gilt. Du darfst in der Induktionsvoraussetzung schreiben: Die Aussage gelte für 1, ..., n. Schließlich gelten ja per Induktionsprinzip zu dem Zeitpunkt, wo wir die Aussage für n+1 beweisen, alle Aussagen bis n.
> Induktionsschritt: n [mm]\to[/mm] n + 1
>
> [mm]\Rightarrow x_{n+1}[/mm] = [mm]\bruch{3^{n+1} - 1}{2}[/mm]
>
> nach Definition gilt: [mm]x_{n+1}[/mm] = [mm]4x_{n}[/mm] - [mm]3x_{n-1}[/mm]
>
> [mm]\Rightarrow \bruch{3^{n+1} - 1}{2}[/mm] = [mm]4x_{n}[/mm] - [mm]3x_{n-1}[/mm]
Du musst anders anfangen, so wird das nichts. Du musst vor allem dann in deinem Beweis klar machen, wo du die Induktionsvoraussetzung verwendest.
Also, wie du schon richtig geschrieben hast, müssen wir nachweisen:
[mm] $x_{n+1} =\bruch{3^{n+1} - 1}{2}$
[/mm]
Dazu beginnen wir folgendermaßen:
[mm] $x_{n+1} [/mm] = [mm] 4*x_{n} [/mm] - [mm] 3*x_{n-1}$
[/mm]
Nun wenden wir die Induktionsvoraussetzung an!!!
$= [mm] 4*\left(\bruch{3^{n} - 1}{2}\right) [/mm] - [mm] 3*\left(\bruch{3^{n-1} - 1}{2}\right)$
[/mm]
Nun musst du nur noch zeigen, dass das gerade $= [mm] \bruch{3^{n+1} - 1}{2}$ [/mm] ist, dann bist du fertig.
Benutze dazu, dass z.B. [mm] $3*3^{x} [/mm] = [mm] 3^{x+1}$ [/mm] ist.
Grüße,
Stefan
|
|
|
| |
|
> Find' ich ja nett, dass sie bei euch in den
> Aufgabenstellungen "bitte" verwenden
Schön, falls es einfach nett und menschen-
freundlich ist. Hoffentlich gibt's keine
Retourkutschen in anderem Zusammenhang ... 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:43 So 25.10.2009 | | Autor: | Doemmi |
Ich denke das "bitte" war eher ein Versehen, das habe ich bisher auch noch nie in einer Aufgabe gesehen
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:42 So 25.10.2009 | | Autor: | Doemmi |
Okay, ich komme nun auf das Ergebnis, aber warum darf ich dank der Induktionsvoraussetzung [mm] x_{n-1} [/mm] = [mm] \bruch{3^{n-1} - 1}{2} [/mm] setzen?
Warum muss ich (im Induktionsanfang?) das auch für n-1 beweisen?
Vielen Dank für die Hilfe!
|
|
|
| |
|
Hallo!
> Okay, ich komme nun auf das Ergebnis, aber warum darf ich
> dank der Induktionsvoraussetzung [mm]x_{n-1}[/mm] = [mm]\bruch{3^{n-1} - 1}{2}[/mm]
> setzen?
Das Prinzip der Induktion funktioniert so, dass du erst annimmst, dass die Aussage für n = 1 stimmt. (Hier müsstest du eigentlich auch noch zeigen, dass die Aussage für n = 2 stimmt). Bei der Induktionsvoraussetzung nimmst du an, dass die Aussage für n stimmt. Es ist aber klar, dass wenn die Induktion bei "n" angekommen ist, sie auch schon bewiesen hat, dass die Aussage für alle vorherigen Zahlen stimmt. Also darfst du bei der Induktionsvoraussetzung auch benutzen, dass die Aussage schon für 1,...,n bewiesen wurde.
> Warum muss ich (im Induktionsanfang?) das auch für n-1
> beweisen?
Beim Induktionsanfang musst du nur die Aussage für n = 1 nachweisen (bzw. hier eigentlich auch noch für n = 2, weil wir n-1 als Induktionsvoraussetzung benutzen).
Grüße,
Stefan
|
|
|
|
