Induktionsbeweis Fibonacci < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:15 Sa 21.10.2006 | | Autor: | dump_0 |
| Aufgabe | Zeigen Sie durch vollständige Induktion
(a) [tex]F_{k+2} \ge \varphi^k , k \in \IN[/tex]
(b) [tex]F_k^2 = F_{k-1}F_{k+1} + (-1)^{k+1} , k \in \IN \backslash\{0,1\}[/tex] |
Hallo!
Ich soll die obige Aufgabe mithilfe vollst. Induktion lösen.
Ich komme leider auf keinen Ansatz bei beiden, wie Induktion funktioniert ist mir klar.
Ich habe noch den Hinweis, dass [mm] F_k [/mm] die k-te Fibonacci-Zahl und [mm] \varphi [/mm] der goldene Schnitt ([tex]\varphi = \bruch{1 + \wurzel{5}}{2}[/tex]) sind.
Kann mir bitte jemand weiterhelfen?
Mfg
|
|
| |
|
> Zeigen Sie durch vollständige Induktion
>
> (a) [tex]F_{k+2} \ge \varphi^k , k \in \IN[/tex]
> (b) [tex]F_k^2 = F_{k-1}F_{k+1} + (-1)^{k+1} , k \in \IN \backslash\{0,1\}[/tex]
> Ich habe noch den Hinweis, dass [mm]F_k[/mm] die k-te Fibonacci-Zahl
> und [mm]\varphi[/mm] der goldene Schnitt ([tex]\varphi = \bruch{1 + \wurzel{5}}{2}[/tex])
> sind.
Hallo,
zunächst einmal die Fibonacci-Zahlen [mm] F_n:
[/mm]
Die Folge der Fibonacci-Zahlen [mm] (F_1, F_2, F_3, F_4, F_5, [/mm] ...) = [mm] (F_n)_{n \in \IN}
[/mm]
ist rekursiv definiert durch
[mm] F_1:=1, F_2:=1, F_n:=F_{n-1}+F_{n-2} [/mm] für n [mm] \ge [/mm] 2.
In Worten ausgedrückt: man erhält die n-te Fibonacci-Zahl, indem man die beiden vorhergehenden addiert, also [mm] (F_n)_{n \in \IN} [/mm] = (1,1,2,3,5,8,13,...)
Das vorweg. Nun zur Aufgabe:
Zu zeigen durch vollständige Induktion ist
> (a) [tex]F_{k+2} \ge (\bruch{1 + \wurzel{5}}{2})^k , k \in \IN[/tex].
Nun, zuerst brauchst Du Deinen Induktionsanfang. Hier mußt Du prufen, ob die Aussage für k=1 gilt, ob also [mm] F_{1+2} \ge (\bruch{1 + \wurzel{5}}{2})^1 [/mm] ,
Tja, da mußt Du eben nachgucken, ob das so ist.
[mm] F_{1+2}=F_3=F_2+F_1=1+1=2=\bruch{4}{2}\le [/mm] ??? [mm] \le \bruch{1 + \wurzel{5}}{2}. [/mm]
Danach folgt der Schritt von k [mm] \to [/mm] k+1.
Du hast hier unter Verwendung der Induktionsvoraussetzung [mm] F_{k+2} \ge \varphi^k [/mm] , k [mm] \in \IN [/mm] zu zeigen, daß
[mm] F_{(k+1)+2} \ge \varphi^{k+1} [/mm] für alle k [mm] \in \IN [/mm] gilt.
Startend mit [mm] F_{(k+1)+2} [/mm] mußt Du so lange (und so geschickt!) abschätzen, daß am Ende [mm] ...\ge \varphi^{k+1} [/mm] dasteht.
Natürlich wirst Du die Def. der Fibonaccizahlen verwenden müssen, z.B. [mm] F_{(k+1)+2}= F_{k+2}+F_{k+1}.
[/mm]
(Nun ahne ich, daß Du Dich an [mm] F_{k+1} [/mm] stoßen wirst. Es ist [mm] F_{k+1}=F_{(k-1)+2} [/mm] und dieser Fall ist für alle k [mm] \in \IN [/mm] \ {1} bereits in der I.V. enthalten. Den Fall k=1 handelst Du eben gesondert ab.)
Ich hoffe, daß ich Dir die größten Steine aus dem Weg geräumt habe.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:10 So 22.10.2006 | | Autor: | dump_0 |
Hallo Angela,
erstmal vielen Dank für deine ausführliche Antwort!
Ich bin leider trotzdem noch nicht zum Ziel gekommen :(
Ich bin jetzt soweit gekommen:
[tex]F_{(k+1) + 2} = F_{k+1} + F_{k+2}[/tex]
[tex]F_{(k+1) + 2} = F_{(k-1) + 2} + F_{k+2}[/tex]
Für [mm] F_{k+2} [/mm] ist die Voraussetzung erfüllt, für [mm] F_{(k-1) + 2} [/mm] ist sie für alle k ausser 1 erfüllt, für k=1 ist sie es nicht mehr wenn man nachrechnet.
Aber hier komme ich dann auch schon nicht mehr weiter :(
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:41 So 22.10.2006 | | Autor: | ullim |
Hi dump,
zu a)
versuchs mal mit mit den Abschätzungen
[mm] F_{k+2}\ge\varphi^k [/mm] und [mm] F_{k+1}\ge\varphi^{k-1}, [/mm] d.h
[mm] F_{k+3}\ge\varphi^k+\varphi^{k-1}=\varphi^{k-1}(\varphi+1) [/mm] und der Tatsache das [mm] \varphi+1=\varphi^2 [/mm] gilt.
Für [mm] F_3 [/mm] musst Du nachweisen das [mm] 2\ge\bruch{1 + \wurzel{5}}{2} [/mm] ist, das sollte gehen.
PS: für die nächste zeit bin ich weg.
mfg ullim
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:04 So 22.10.2006 | | Autor: | ullim |
Hi dump,
bin noch nicht ganz weg.
Zu b)
Zu beweisen ist, das
[mm] F_{k+1}^2=F_k*F_{k+2}+(-1)^{k+2} [/mm] gilt unter Annahme der Gültigkeit der IV.
Also es gilt (nur eine Beweisskizze wegen Zeitmangel)
[mm] F_k*F_{k+2}+(-1)^{k+2}=F_k*(F_{k+1}+F_{k})+(-1)^{k+2}=F_{k-1}F_{k+1}+(-1)^{k+1}+F_{k}F_{k+1}+(-1)^{k+2}=F_{k+1}^2
[/mm]
Ich hoffe es hilft
mfg ullim
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:44 So 22.10.2006 | | Autor: | dump_0 |
Danke für die Antwort!
Die a) habe ich jetzt lösen können, bei der b) blicke ich allerdings noch nicht so ganz durch:
[tex]F_{k+1}^2 = F_k F_{k+2} + (-1)^{k+2}[/tex]
[tex] = F_k (F_k + F_{k+1}) + (-1)^{k+2}[/tex]
[tex] = F_k^2 + F_k F_{k+1} + (-1)^{k+2}[/tex]
[tex] = F_{k-1} F_{k+1} + (-1)^{k+1} + F_k F_{k+1} + (-1)^{k+2}[/tex]
Allerdings verstehe ich jetzt nicht wie man einfach auf [mm] F_{k+1}^2 [/mm] schlussfolgern kann?
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:33 So 22.10.2006 | | Autor: | ullim |
Hi dump,
[mm] F_{k-1}F_{k+1}+(-1)^{k+1}+F_kF_{k+1}+(-1)^{k+2}=F_{k+1}(F_{k-1}+F_k)+(-1)^{k+1}+(-1)^{k+2}
[/mm]
wegen [mm] F_{k+1}=F_{k-1}+F_k [/mm] (s. Definition der Fibonacci Folge) und
[mm] (-1)^{k+1}+(-1)^{k+2}=0 [/mm] (einmal kommt -1 und einmal +1 heraus) folgt, der Ausdruck wird [mm] F_{k+1}^2
[/mm]
mfg ullim
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:44 So 22.10.2006 | | Autor: | dump_0 |
Oh mein Gott, da muss ich fast schämen, ich danke dir!!
Ich habe garnicht darauf geachtet, dass die -1 einmal mit geradem und einmal mit ungeradem Exponenten vorkommt und das ja 0 ergibt, aber jetzt weiß ich wenigstens wie du auf das Ergebnis gekommen bist :)
Grüße
|
|
|
|
