Vollständige Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:38 So 05.06.2005 | | Autor: | Dr.Ufo |
Hallo erstmal!!!
Ich soll mit vollständiger Induktion zeigen, dass folgendes gilt:
f(h)=1 für h=0
f(h)=2 für h=1
f(h)=4 für h=2
f(h)=f(h-1)+f(h-2)+f(h-3)+1 für h [mm] \ge3
[/mm]
dann ist [mm] f(h)\ge \wurzel{2}^h
[/mm]
Den Induktionsanfang bekomm ich durch nachrrechnen hin.
Aber wenn ich dann als Induktionsschritt von h nach h+1 gehe stehe ich vor folgendem Problem:
f(h+1-1)+f(h+1-2)+f(h+1-3)+1
[mm] \gdw [/mm] f(h) +f(h-1) +f(h-2) +1 (nach Ind.vorraussetzung:)
[mm] \ge \wurzel{2}^h [/mm] +f(h-1)+f(h-2)+1
wie soll ich jetzt weiter umformen, so dass ich erhalte:
[mm] \ge \wurzel{2}^{h+1}
[/mm]
Würd mich sehr über einen Tip freuen!!!
Danke schon mal!
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:51 So 05.06.2005 | | Autor: | Hanno |
Hallo Ufo ;)
> f(h+1-1)+f(h+1-2)+f(h+1-3)+1
> $ [mm] \gdw [/mm] $ f(h) +f(h-1) +f(h-2) +1 (nach Ind.vorraussetzung:)
> $ [mm] \ge \wurzel{2}^h [/mm] $ +f(h-1)+f(h-2)+1
Was machst du hier? Ich nehme an du meinst folgendes:
$f(h+1)=f(h)+f(h-1)+f(h-2)+1$,
und nun versuchst du
[mm] $f(h+1)\geq \sqrt{2}^{h+1}$
[/mm]
[mm] $\gdw =f(h)+f(h-1)+f(h-2)+1\geq \sqrt{2}^{h+1}$
[/mm]
zu zeigen.
Angefangen hast du auch schon richtig, doch was hindert dich daran, nicht auch noch $f(h-1)$ und $f(h-2)$ durch [mm] $\sqrt{2}^{h-1}$ [/mm] bzw. [mm] $\sqrt{2}^{h-2}$ [/mm] nach unten abzuschätzen? Versuche das bitte einmal - die resultierende Ungleichung ist nicht schwierig zu beweisen.
Liebe Grüße,
Hanno
|
|
|
|
