Fibonacci. vollständige Ind. < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:39 Sa 12.05.2012 | | Autor: | Stift |
Hallo, ich soll beweisen, dass [mm] Fn\le 2^{n-1} [/mm] , dabei gilt [mm] F_{0}=F_{1}=1 [/mm] und [mm] F_{n+1}=F_{n}+F_{n-1}
[/mm]
Also den Induktionsanfang habe ich. Nur beim Ind.schritt hänge ich:
n->n+1 : [mm] F_{n+1} \le 2^{n} [/mm]
[mm] F_{n+1}=F_{n}+F_{n-1} \le 2^{n-1}+F_{n-1} [/mm] und ab hier weiß ich nicht weiter wie ich abschätzen soll.
Lg
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:55 Sa 12.05.2012 | | Autor: | Blech |
> $ [mm] F_{n+1}=F_{n}+F_{n-1} \le 2^{n-1}+F_{n-1} [/mm] $ und ab hier weiß ich nicht weiter wie ich abschätzen soll.
[mm] $F_{n-1}\leq 2^{n-2}$ [/mm] nach Induktionsvoraussetzung.
Was steht dann rechts?
ciao
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:09 Sa 12.05.2012 | | Autor: | Stift |
Hallo, danke erstmal.
Dann steht da [mm] \le 2^{n-1}+2^{n-2} [/mm] = [mm] 2^{n}(1/2+1/4)=2^{n}*3/4 [/mm] Aber jetzt habe ich doch schon mehr als [mm] 2^{n}, [/mm] wo ich eigentlich hin wollte oder was habe ich falsch gemacht??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:28 Sa 12.05.2012 | | Autor: | teo |
> Hallo, danke erstmal.
> Dann steht da [mm]\le 2^{n-1}+2^{n-2}[/mm] =
> [mm]2^{n}(1/2+1/4)=2^{n}*3/4[/mm] Aber jetzt habe ich doch schon
> mehr als [mm]2^{n},[/mm] wo ich eigentlich hin wollte oder was habe
> ich falsch gemacht??
Du darfst hier nicht [mm] 2^n [/mm] ausklammern sondern [mm] 2^{n-2}:
[/mm]
[mm]\le 2^{n-2}(2+1)[/mm] wie kannst du das jetzt noch geschickt abschätzen damit da [mm]\le 2^n[/mm] steht?
Grüße
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:51 Sa 12.05.2012 | | Autor: | Stift |
Danke, aber ich kriege da wirklich keine sinnvolle Abschätzung hin. Kriege immer nur das selbe wie im vorigen Beitrag. Hast du vielleicht noch einen Tipp??
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:04 Sa 12.05.2012 | | Autor: | teo |
[mm]2^{n-2}(2+1) \le 2^{n-2}(2+2)=2^{n-2}(4)=2^{n-2}2^2=2^n[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:08 Sa 12.05.2012 | | Autor: | Stift |
Vielen Dank.
Auf so was komme ich nicht, aber jetzt ist das klar.
Lg
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:45 Sa 12.05.2012 | | Autor: | teo |
Hallo,
du musst bei sowas wenn du nicht weier kommst von hinten anfangen. also wenn du [mm] 2^{n-2} [/mm] hast und [mm] 2^n [/mm] brauchst fehlen dir also noch [mm] 2^2 [/mm] und dann musst halt mal rumprobieren wie du die am besten herbekommst. und bei dieser ausklammerei ist es meistens am geschicktesten die niedrigste potenz auszuklammern...
viele grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:50 Sa 12.05.2012 | | Autor: | Stift |
Toll, danke für die Tipps, die werd ich mir merken:)
Lg
|
|
|
|
