| Autor |
Beitrag |
    
Nadine (anja)
Junior Mitglied
Benutzername: anja
Nummer des Beitrags: 25
Registriert: 11-2001
| | Veröffentlicht am Dienstag, den 16. April, 2002 - 15:48: | 
|
Hallo habe ein Problem mit der folgenden Aufgabe:
a) Man beweise für die Folge der Fibionacci- Zahlen folgende explizite Formel durch vollständige Induktion:
Fn= 1/Wurzel 5 ((s+Wurzel5/2)^n - (1-Wurzel5/2)^n)
b) Man leite aus a) eine Laufzeitschranke für den euklidischen Algorithmus ab.
Bitte helft mir Nadine |
Martin (martin243)
Fortgeschrittenes Mitglied
Benutzername: martin243
Nummer des Beitrags: 91
Registriert: 02-2001
| | Veröffentlicht am Dienstag, den 16. April, 2002 - 19:45: |
|
Hi Nadine!
Bei der a) kann ich dir helfen, aber nicht bei der b):
Als erstes würde ich folgende Schreibweise einführen:
f1 = (1+Wurzel(5))/2
f2 = (1-Wurzel(5))/2
Damit sieht die Formel so aus:
Fn = 1/W(5) * (f1n - f2n)
Als nächstes folgende Beziehungen (einfach nachrechnen):
1 + f1 = f12
1 + f2 = f22
Wir beginnen mit dem Induktionsanfang:
Hier muss man die Richtigkeit für n=0 und n=1 zeigen:
n=0:
1/W(5) * (f10 - f20)
= 1/W(5) * (1 - 1)
= 0 (stimmt)
n=1:
1/W(5) * (f11 - f21)
= 1/W(5) * (f1 - f2)
= 1/W(5) * W(5)
= 1 (stimmt auch)
Wenn ihr bei der 1 anfangt, dann musst du n=1 und n=2 für den Induktionsanfang nehmen.
Nun zum Induktionsschritt:
Fn+2 = 1/W(5) * (f1n+2 - f2n+2)
= 1/W(5) * f1n+2 - 1/W(5) * f2n+2
= 1/W(5) * f1n * f12 - 1/W(5) * f2n * f22
nun kommen obige Beziehungen ins Spiel:
= 1/W(5) * f1n * (1 + f1) - 1/W(5) * f2n * (1 + f2)
= 1/W(5) * f1n + 1/W(5) * f1n * f1 - 1/W(5) * f2n - 1/W(5) * f2n * f2
= 1/W(5) * f1n + 1/W(5) * f1n+1 - 1/W(5) * f2n - 1/W(5) * f2n+1
= 1/W(5) * f1n - 1/W(5) * f2n + 1/W(5) * f1n+1 - 1/W(5) * f2n+1
= 1/W(5) * (f1n - f2n) + 1/W(5) * (f1n+1 - f2n+1)
= Fn + Fn+1
Und das wollten wir doch sehen, oder?!
|
Nadine (anja)
Mitglied
Benutzername: anja
Nummer des Beitrags: 29
Registriert: 11-2001
| | Veröffentlicht am Mittwoch, den 17. April, 2002 - 14:50: |
|
Danke |
