Fibonacci-Zahlen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) für Interessierte  | | Datum: | 20:19 Sa 23.10.2010 | | Autor: | qwe123 |
Hallo, könnt Ihr mir helfen folgen Aussagen über Fibonacci-Zahlen zu beweisen.
a) [mm] \forall [/mm] n [mm] \in \IN [/mm] : [mm] F(n)\le 2^n
[/mm]
b) [mm] \forall [/mm] n [mm] \ge [/mm] 11 : 2^nF(n) [mm] \ge 3^n
[/mm]
(F(n) sind dabei die Fibonacci-Zahlen))
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:25 Sa 23.10.2010 | | Autor: | Loddar |
Hallo qwe123,
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !!
Hast Du Dir mal unsere Forenregeln durchgelesen?
Was sind denn Deine konkreten Fragen, was hast Du Dir bisher dazu überlegt und wie sehen Deine Ansätze aus?
Denn zumindest den Induktionsanfang solltest Du doch hinbekommen.
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:23 Sa 23.10.2010 | | Autor: | qwe123 |
Der Induktionsanfang ist nicht das Problem. Das Problem ist im Induktionsschritt. Z.B. bei a) Wenn [mm] F(n)\le 2^n [/mm] gilt [mm] \Rightarrow F(n+1)\le [/mm] 2^(n+1) [mm] \Rightarrow F(n)+F(n-1)\le 2^n [/mm] *2
weiter komme ich jedoch nicht. Ich muss vermutlich die F-Funktion umformen - weiß aber nicht wie.
|
|
|
| |
|
Hallo qwe123,
> Der Induktionsanfang ist nicht das Problem. Das Problem ist
> im Induktionsschritt. Z.B. bei a) Wenn [mm]F(n)\le 2^n[/mm] gilt
> [mm]\Rightarrow F(n+1)\le[/mm] 2^(n+1) [mm]\Rightarrow F(n)+F(n-1)\le 2^n[/mm]
> *2
> weiter komme ich jedoch nicht. Ich muss vermutlich die
> F-Funktion umformen - weiß aber nicht wie.
Wende doch einfache die Induktionsvoraussetzung an.
Es gilt [mm]F\left(n\right) \le 2^{n}[/mm] und [mm]F\left(n-1\right) \le 2^{n-1}[/mm]
Damit wird
[mm]{F(n)+F(n-1) \le 2^{n}+2^{n-1} \le}\ ... [/mm]
Gruss
MathePower
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:32 Sa 23.10.2010 | | Autor: | qwe123 |
Meine Voraussetzung ist [mm] F(n)\le 2^n [/mm] -ja aber ist damit auch [mm] F(n-1)\le [/mm] 2^(n-1) meine Vorausetzung? Ich dachte ich kann immer nur von einem ausgehen?
|
|
|
| |
|
> Meine Voraussetzung ist [mm]F(n)\le 2^n[/mm] -ja aber ist damit auch
> [mm]F(n-1)\le[/mm] 2^(n-1) meine Vorausetzung? Ich dachte ich kann
> immer nur von einem ausgehen?
Die Idee der Beweismethode mit vollständiger Induktion beruht
ja darauf, dass die einzelnen Aussagen A(n) für n=1, n=2, n=3, ...
in dieser Reihenfolge bewiesen werden, nämlich A(1) durch die
Verankerung und jedes A(n+1) aus dem vorangehenden A(n) durch
den Induktionsschritt. Wenn man also in dieser Weise schrittweise
vorgegangen ist, darf man an der Stelle, wo A(n) schon bewiesen
ist, ohne weiteres auch annehmen, dass alle früheren Aussagen,
also A(1), A(2), A(3), ...... bis und mit A(n-1) ebenfalls feststehen.
LG Al-Chw.
|
|
|
| |
|
> Der Induktionsanfang ist nicht das Problem. Das Problem ist
> im Induktionsschritt. Z.B. bei a) Wenn [mm]F(n)\le 2^n[/mm] gilt
> [mm]\Rightarrow F(n+1)\le\ 2^{n+1}\ \ \Rightarrow F(n)+F(n-1)\le 2^n\ *\ 2[/mm]
Bist du dir bewusst, dass du hier die Idee des Induktionsbeweises
zo ziemllich exakt auf den Kopf stellst ?
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:12 Sa 23.10.2010 | | Autor: | qwe123 |
IA: n=0 [mm] F(0)\le 2^0 F(0)=0\le 2^0=1 [/mm] -wahr
IS: Wenn [mm] F(n)\le 2^n [/mm] gilt [mm] \Rightarrow F(n+1)\le [/mm] 2^(n+1)
[mm] F(n+1)=F(n)+F(n-1)\le 2^{n+1}=2^n [/mm] *2 = [mm] 2^n [/mm] + [mm] 2^n
[/mm]
da [mm] F(n)\le 2^n [/mm] Voraussetzung ist muss ich nur noch zeigen das F(n-1) ebenfalls [mm] \le 2^n [/mm] ist - aber wie?
bis hier hin bin ich gekommen - aber du sagst mir nun das dieser Weg den Induktionsbeweis auf den Kopf stellt? Was mache ich den falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:20 Sa 23.10.2010 | | Autor: | Loddar |
Hallo qwe!
Wann und wo verwendest Du denn die Induktionsvoraussetzung? Das ist elementar im Induktionsschritt.
Gruß
Loddar
|
|
|
| |
|
Hallo qwe,
außer Loddars elementarem Hinweis hätte ich noch eine Frage:
Kannst Du zeigen, dass [mm] F_{n+1}>F_{n} [/mm] ist?
Dann wärst Du ja auch fertig.
Eine wirklich elegante Lösung ist das alles aber noch nicht, immerhin kurz genug für die Fragestellung.
Grüße
reverend
|
|
|
|
