Fibonacci
Darstellungen einer Zahl (Ende)
Die Ableitung (**) auf der vorigen Seite liefert die nächste allgemeine Formel:
F1 + F3 + F5 + ... + F2n+1 = F2n+2 und
F1 + F2 + F3 + ... + Fn = Fn+2 - 1
und daraus geht unmittelbar hervor dass
F2 + F4 + F6 + ... + F2n = F2n+1 - 1
Wenn jede Zahl dargestellt werden kann als Summe von verschiedenen Fibonaccizahlen, dann ist die nächste Frage,
in wievielen Weisen kann eine Zahl a dargestellt werden.
Wir werden diese Anzahl notieren mit m(a).
Es seien k und n positive ganze Zahlen und k<Fn.
Wir untersuchen die Räpresentationen von a = Fn+2 - k.
We betrachten zuerst die Darstellungen wobei der Term Fn+1 nicht auftretet. Wir wissen, dass
F1 + F2 + F3 + ... + Fn = Fn+2 - 1, (***)
also können wir alle Darstellungen ohne den Term Fn+1 finden door
Aufzählung von allen Darstellungen von k-1 und diese Darstellungen von (***) zu subtrahieren.
Jetzt noch die Darstellung mit einem Term Fn+1. Es gilt dass a = Fn+1 + Fn - k.
Diese Anzahl ist also m(Fn - k).
Kurz: m(Fn+2 - k) = m(k-1) + m(Fn - k)
Die Formel ist auch gültig für k=0 wenn wir definieren m(-1)=1.
Wenn wir m(i) kennen für i zwischen Fn und Fn+1 dann liefert die abgeleitete Recursion
alle Werte m(i) mit i zwischen Fn+1 und Fn+2.
Überdies (ohne Beweis) m(Fn+2 - k) = m(Fn+1 + k - 1) für 0 < k <= Fn
Damit wir die m(i)'s schnell berechnen können, machen wir Gebrauch von der Formel
(1 + x F1 ) (1 + x F2 ) ... (1 + x Fr ) = 1 + m(1)x + m(2)x2 + ... + m(Fr+1-1)xFr+1-1 +
(m(Fr+1) - m(1))xFr+1 +
(m(Fr+1+1) - m(2))xFr+1+1 +
(m(Fr+2-1) - m(Fr))xFr+2-1
Wenn Sie noch andere Eigenschaften der Funktion m(i) ableiten können, erfahre ich das gerne.
Zum Schluß fragen wir uns ob es eine Zahl z gibt so, dass jede Zahl als Summe von maximal z verschiedenen Fibonaccizahlen dargestellt
werden kann. Wohlan, F1 + F2 + F3 + ... + F2n-2 = F2n - 1
Die Anzahl Terme für F2n - 1 kann nur reduziert werden indem man den Term F2n-1 benutzt. Dann ist
F2n - 1 = F2n-1 + (F2n-2 - 1). Für F2n-2 - 1 gilt wieder die gleiche Geschichte.
Die minimale Räpresentation für F2n - 1 ist also F2n-1 + F2n-3 + ... + F3.
Die Anzahl Terme wächst mit n.