Fibonacci-Zahlen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:43 So 24.10.2010 | | Autor: | wilfi |
hallo
ich habe eine aufgabe bei der ich einfach nicht weiterkomme...
ich habe sie bereits in einem anderen forum gestellt, jedoch komme ich immernoch nicht weiter.
hier meine frage:
Die Menge der Fibonacci-Zahlen F(n) ist rekursiv definiert durch
F(0):=0
F(1):=1
F(n+2):=F(n+1)+F(n)
Beweisen Sie mit vollstaendiger Induktion:
(a) F(n)≤2 hoch n(n Element aus N)
(b) 2 hoch nF(n)≥3 hoch n;n>11
mein lösungsansatz für (b)
Induktionanfang:
n=11
2hoch 11⋅F(11)≥311
182272≥177147
Induktionsschritt:
2n+1⋅F(n+1)≥3 hoch (n+1)
dann komme ich nicht mehr weiter ...
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
http://www.onlinemathe.de/forum/Fibonacci-Zahlen-16
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:55 So 24.10.2010 | | Autor: | Lyrn |
> hier meine frage:
> Die Menge der Fibonacci-Zahlen F(n) ist rekursiv definiert
> durch
> F(0):=0
> F(1):=1
> F(n+2):=F(n+1)+F(n)
>
> Beweisen Sie mit vollstaendiger Induktion:
>
> (a) F(n)≤2 hoch n(n Element aus N)
> (b) 2 hoch nF(n)≥3 hoch n;n>11
Es wäre hilfreich wenn du den Formeleditor benutzt.
Fang doch erstmal mit Aufgabenteil a) an, b) geht dann ja fast äquivalent.
Du beginnst mit
Induktionsanfang:
Sei [mm]n=0[/mm]
[mm]F(0)=0 \le 2^{0}=1 [/mm]
Induktionsvorraussetzung:
Für ein beliebiges, aber festes n [mm] \in \IN [/mm] gilt: [mm] F(n)\le 2^{n}
[/mm]
Induktionsschritt:
[mm]n \to n+1[/mm]
Jetzt benutzt du die Induktionsvorraussetzung und kommst dann recht schnell zum Ziel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:47 So 24.10.2010 | | Autor: | wilfi |
danke für deine Antwort
daraus folgt dann
F(n+1)<= 2^(n+1)
durch F(n+2):=F(n+1)+F(n)
komme ich auf F(n+1)=F(n)+F(n-1)
--> F(n)+F(n+1)= 2^(n+1)
ist das so richtig
und wie mache ich weiter ?
|
|
|
| |
|
Hallo wilfi und ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") ,
> danke für deine Antwort
>
> daraus folgt dann
> F(n+1)<= 2^(n+1)
> durch F(n+2):=F(n+1)+F(n)
> komme ich auf F(n+1)=F(n)+F(n-1) ![[ok]](/images/smileys/ok.gif "[ok]")
> --> F(n)+F(n+1)= 2^(n+1)
Na, du musst doch irgendwie mal die Induktionsvoraussetzung ins Spiel bringen, du hast für alle [mm]k\le n[/mm]: [mm]F_k\le 2^k[/mm]
Also insbesondere [mm]F_n\le 2^n[/mm] und [mm]F_{n-1}\le 2^{n-1}[/mm]
Das benutze nun in [mm]F_{n+1}=F_{n-1}+F_n\le ... + ... \le ... = 2^{n+1}[/mm]
>
> ist das so richtig
> und wie mache ich weiter ?
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:21 So 24.10.2010 | | Autor: | wilfi |
Danke für die tolle Begrüßung :)
setze ich jetzt für F(n-1) einfach 2^(n-1) und bin damit am Ende meines Beweises angelangt oder mache ich es mir damit zu einfach ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:29 So 24.10.2010 | | Autor: | Lyrn |
Du kann [mm] 2^{n+1} [/mm] auch schreiben als [mm] 2^{n}*2^{1}=2^{n}*2
[/mm]
Jetzt kannst du deine Induktionsvorraussetzung anwenden:
F(n+1)=F(n)+F(n-1)
[mm] 2^{n+1}=2^{n}*2
[/mm]
...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:54 So 24.10.2010 | | Autor: | wilfi |
also meine Lösung wäre :
[mm] F(n+1)=F(n-1)+F(n)<=2F(n)<=2*2^n=2^n+2^n
[/mm]
daraus folgt : [mm] F(n)<=2^n
[/mm]
ist das richtig ?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:41 So 24.10.2010 | | Autor: | Loddar |
Hallo wilfi!
Dieser Weg ist so möglich. Dafür musst Du aber bewiesen haben, dass gilt $F(n) \ [mm] \ge [/mm] \ F(n-1)$ (sprich: die Monotonie der Fibonacci-Folge).
Ein anderer Weg ist z.B. hier zu sehen.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:58 So 24.10.2010 | | Autor: | wilfi |
okay vielen dank für die geduld ;)
|
|
|
|
