Fibonacci Induktion < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Die Folge der Fibonacci-Zahlen ist definiert durch
[mm] f_{0}=1
[/mm]
[mm] f_{1}=1
[/mm]
[mm] f_{n}=f_{n-1}+f_{n-2} [/mm] für [mm] n\ge [/mm] 2 .
Beweisen Sie die folgenden Aussagen.
a) Für alle [mm] n\in [/mm] N gilt [mm] f_{n}\le 2^{n}
[/mm]
b) Für alle [mm] n\ge [/mm] 11 gilt [mm] f_{n}\ge \bruch{3}{2}^{n} [/mm] |
Hallo.
Ich versuche die Aussagen induktiv zu beweisen und habe auch einen Ansatz hinbekommen.
Allerdings habe ich jetzt Probleme im letztem Schritt (bei beiden Beweisen):
a) z.Z.: [mm] A(n)=f_{n}\le 2^{n}, \forall n\in [/mm] N
IA: n=2:
[mm] f_{2}\le 2^{2}
[/mm]
[mm] \gdw f_{1}+f_{0}\le [/mm] 4
[mm] \gdw [/mm] 1<4 w.A.
IB: [mm] A(n)=f_{n}\le 2^{n}, \forall n\in [/mm] N
IS: A(n+1):
[mm] f_{n+1}\le 2^{n+1}
[/mm]
[mm] f_{n}+f_{n-1}\le 2^{n}\cdot [/mm] 2
[mm] f_{n-1}+f_{n-2}+f_{n-1}\le 2^{n}\cdot [/mm] 2
[mm] 2f_{n-1}+f_{n-2}\le 2^{n}\cdot [/mm] 2
Ab hier klemmt die Säge.
b) z.Z.: [mm] A(n)=f_{n}\ge (\bruch{3}{2})^{n}, n\ge [/mm] 11
IA: n=11:
[mm] f_{11}\ge (\bruch{3}{2})^{11}
[/mm]
[mm] \gdw f_{10}+f_{9}\ge (\bruch{3}{2})^{11}
[/mm]
[mm] \gdw 89\ge (\bruch{3}{2})^{11} [/mm] w.A.
IB: [mm] A(n)=f_{n}\ge (\bruch{3}{2})^{n}, n\ge [/mm] 11
IS: A(n+1):
[mm] f_{n+1}\ge (\bruch{3}{2})^{n+1}
[/mm]
[mm] \gdw f_{n}+f_{n-1}\gdw (\bruch{3}{2})^{n}\cdot \bruch{3}{2}
[/mm]
[mm] \gdw [/mm] ...
[mm] \gdw 2f_{n-1}+f_{n-2}\ge (\bruch{3}{2})^{n}\cdot \bruch{3}{2}
[/mm]
Und ab hier klemmt auch die Säge.
Über Hilfe würde ich mich vin daher sehr freuen. 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:37 Mo 02.11.2015 | | Autor: | sissile |
Beginne doch gleich mit n=0 beim Induktionsanfang:
I.Anfang: [mm] f_0=1=2^0 \le 2^0
[/mm]
> z.Z.: $ [mm] A(n)=f_{n}\le 2^{n}, \forall n\in [/mm] $ N
> IA: n=2:
> $ [mm] f_{2}\le 2^{2} [/mm] $
> $ [mm] \gdw f_{1}+f_{0}\le [/mm] $ 4
> $ [mm] \gdw [/mm] $ 1<4 w.A.
In der Angabe steht aber [mm] f_0=1? [/mm] Dann würde bei der letzten Ungleichung [mm] 2\le [/mm] 4 stehen
Induktionsschritt:
[mm] f_{n+1}=f_n+f_{n-1} \overbrace{\le}_{\mbox{IV. }} 2^n [/mm] + [mm] 2^{n-1}=2^{n-1} [/mm] (2+1)< [mm] 2^{n-1}*4 [/mm] = [mm] 2^{n+1}
[/mm]
b) funktioniert analog
LG,
sissi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:30 Mo 02.11.2015 | | Autor: | fred97 |
Ergänzend zu meiner Vorrednerin:
Du schreibst
"IB: $ [mm] A(n)=f_{n}\le 2^{n}, \forall n\in [/mm] $ N "
1. "A(n)=... " was soll das bedeuten ???
2. Die Induktionsvoraussetzung lautet nicht
[mm] f_n \le 2^n \forall n\in \IN
[/mm]
!!!
Wenn Du das voraussetzt, brauchst Du nix mehr zeigen !!
Wie lautet die I.V: korrekt ?
FRED
|
|
|
| |
|
Danke sehr schon mal für die Reaktionen.
>1. "A(n)=... " was soll das bedeuten ???
A(n) meint die Aussage(funktion), also das, was zu zeigen ist.
>2. Die Induktionsvoraussetzung lautet nicht $ [mm] f_n \le 2^n \forall n\in \IN [/mm] $ !!!
Meint Induktionsvoraussetzung = Induktionsbehauptung?
Leider ist da die Terminilogie nicht eindeutig.
Jedenfalls werde ich es mal probieren, wobei ich nicht verstehe, wie die Rechnung beim Induktionsschritt aus a) zustande kommt.
Eine Erläuterung wäre nett.
Und zu deiner Frage:
Liegt es am Quantor?
Dann würde IB wohl so aussehen: [mm] $A(n)=f_{n}\le 2^{n}, \exists n\in [/mm] N$
Gruß
|
|
|
| |
|
Hallo,
> Danke sehr schon mal für die Reaktionen.
>
> >1. "A(n)=... " was soll das bedeuten ???
> A(n) meint die Aussage(funktion), also das, was zu zeigen
> ist.
Ja
>
> >2. Die Induktionsvoraussetzung lautet nicht [mm]f_n \le 2^n \forall n\in \IN[/mm]
> !!!
> Meint Induktionsvoraussetzung = Induktionsbehauptung?
Nein ...
> Leider ist da die Terminilogie nicht eindeutig.
Statt I.-voraussetzung sagt man m.W. nach auch I.-verankerung ...
>
> Jedenfalls werde ich es mal probieren, wobei ich nicht
> verstehe, wie die Rechnung beim Induktionsschritt aus a)
> zustande kommt.
>
> Eine Erläuterung wäre nett.
In der Induktion ist zu zeigen:
1) Es gilt [mm]A(0)[/mm] - der Induktionsanfang
2)
a) Es gelte [mm]A(n)[/mm] für ein beliebiges, aber festes [mm]n\in\IN[/mm] - die Induktionsvoraussetzung
b) DANN (also unter dieser Voraussetzung) gilt auch [mm]A(n+1)[/mm]
Sind 1) und 2) erfüllt, so gilt die Beh. für alle [mm] $n\in\IN$
[/mm]
>
> Und zu deiner Frage:
> Liegt es am Quantor?
> Dann würde IB wohl so aussehen: [mm]A(n)=f_{n}\le 2^{n}, \exists n\in N[/mm]
Nein ...
IV: Sei [mm]n\in\IN[/mm] und gelte [mm]A(n)[/mm], also [mm]f_n\le 2^n[/mm]
Zu zeigen ist nun im Induktionsschritt von [mm]n\to n+1[/mm], dass unter dieser IV gefälligst auch die Beh. für [mm]n+1[/mm] gilt, dass also [mm]f_{n+1}\le 2^{n+1}[/mm] gilt.
Dazu setze mal [mm]f_{n+1}[/mm] an und nutze die IV, um das letztlich abzuschätzen als [mm]\le 2^{n+1}[/mm]
>
> Gruß
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:25 Mo 02.11.2015 | | Autor: | Ne0the0ne |
Vielen Dank für eure Hilfe.
Ich konnte die Aufgabe lösen.
Wegen der Formalität rede ich mal mit meinem Übungsleiter.
Gruß :)
|
|
|
|
