Kleine Frage zur Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:21 Do 04.11.2010 | | Autor: | Ersti10 |
| Aufgabe | Beweisen Sie, dass [mm] x_{n}\le 2^{n} [/mm] gilt für alle n [mm] \in \IN
[/mm]
(Weiterführung zur Fibonacci-Folge)
Gegeben ist [mm] x_{n} [/mm] = [mm] x_{n-1} [/mm] + [mm] x_{n-2} [/mm] |
Habe den Induktionsanfang geschafft, beim Induktionsschritt die Annahme und die Behauptung auch aufgestellt.
Nun habe ich eine Frage zum Beweis!
Ich muss ja (n+1) einsetzen um es zu beweisen.
Meine Rechnung:
[mm] x_{n} \Rightarrow x_{n-1} [/mm] + [mm] x_{n-2}
[/mm]
Nun setze ich (n+1) ein und erhalte
[mm] x_{n} [/mm] + [mm] x_{n-1}
[/mm]
Darf ich das dann wie folgt umformen um zur Lösung zu kommen?
[mm] x_{n} [/mm] + [mm] x_{n-1} [/mm] = [mm] x_{n} [/mm] + [mm] x_{n} [/mm] * [mm] x_{-1}
[/mm]
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo,
> Beweisen Sie, dass [mm]x_{n}\le 2^{n}[/mm] gilt für alle n [mm]\in \IN[/mm]
>
> (Weiterführung zur Fibonacci-Folge)
> Gegeben ist [mm]x_{n}[/mm] = [mm]x_{n-1}[/mm] + [mm]x_{n-2}[/mm]
> Habe den Induktionsanfang geschafft, beim
> Induktionsschritt die Annahme und die Behauptung auch
> aufgestellt.
>
> Nun habe ich eine Frage zum Beweis!
>
> Ich muss ja (n+1) einsetzen um es zu beweisen.
> Meine Rechnung:
> [mm]x_{n} \Rightarrow x_{n-1}[/mm] + [mm]x_{n-2}[/mm]
![[haee]](/images/smileys/haee.gif "[haee]")
Was bedeutet [mm]\Rightarrow[/mm] hier?
> Nun setze ich (n+1) ein und erhalte
> [mm]x_{n}[/mm] + [mm]x_{n-1}[/mm]
>
> Darf ich das dann wie folgt umformen um zur Lösung zu
> kommen?
> [mm]x_{n}[/mm] + [mm]x_{n-1}[/mm] = [mm]x_{n}[/mm] + [mm]x_{n}[/mm] * [mm]x_{-1}[/mm]
Benutze die erweiterte Induktionsvoraussetzung:
Sei [mm]n\in\IN[/mm] bel., aber fest und gelte für alle [mm]k\le n[/mm]: [mm]x_k\le 2^k[/mm]
Also insbesondere [mm]x_n\le 2^n[/mm] und [mm]x_{n-1}\le 2^{n-1}[/mm]
Damit [mm]x_{n+1}=x_n+x_{n-1}\le 2^n+2^{n-1}\le 2^n+2^n\ldots[/mm]
>
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Gruß
schachuzipus
|
|
|
| |
|
Hallo Ersti!
> Darf ich das dann wie folgt umformen um zur Lösung zu kommen?
> [mm]x_{n}[/mm] + [mm]x_{n-1}[/mm] = [mm]x_{n}[/mm] + [mm]x_{n}[/mm] * [mm]x_{-1}[/mm]
![[eek]](/images/smileys/eek.gif "[eek]") Nein, das darfst Du nicht. Bedenke, dass $n-1_$ hier ein Index ist und keine Hochzahl.
Daher darfst Du das nicht mit irgendwelchen  Potenzgesetzen verwechslen und verarbeiten.
Gruß vom
Roadrunner
|
|
|
|
