hi,
wie kann ich denn mit der rekursiven die explizite form beweisen oder halt herleiten? man findet zwar ziemlich viel material über den beweis mit vollständiger induktion usw aber irgendwie hab ich keine herleitung aus der rekursiven form gefunden…
Wie geht das?wo könnte das sthen?
alex
Hallo,
ein guter und ausführlicher Beweis steht in „The Art of Computer Programming. Volume 1: Fundamental Algorithms“ von Donald E Knuth ISBN:0-201-89683-4 Buch anschauen (gibts auch auf deutsch) in den mathematischen Vorbemerkungen.
HTH,
Moritz
…mhh…blöd…ich bräuchts aber bis montag?!
hi,
wie kann ich denn mit der rekursiven die explizite form
beweisen oder halt herleiten? man findet zwar ziemlich viel
material über den beweis mit vollständiger induktion usw aber
irgendwie hab ich keine herleitung aus der rekursiven form
gefunden…Wie geht das?wo könnte das sthen?
Hausaufgabe? Also Tipp: die Fibonacci-Folge ist linear-rekursiv, d.h. sie laesst sich explizit formulieren als Matrix-Gleichung:
F_n = M^n * F_0
wobei F_n ein 2-Vektor mit den Fibonacci-Zahlen f_(n-1) und f_n ist, F_0 ist entsprechend der Vektor mit f_0, f_1 und M ist die Koeffizientenmatrix.
Die explizite Formel für die Fibonacci-Folge zu finden, reduziert sich hier auf die explizite Formulierung von M^n. Potenzen von Matrizen zu berechnen führt auf eine EIgenwertgleichung.
Viele Grüße
Oliver T.
alex