Fibonacci
Musterwiederholung:
Wir haben gesehen, dass wenn wir jede Fibonaccizahl durch 4 dividieren, dann bekommen wir die Reste:
1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, ...
Das Muster 1, 1, 2, 3, 1, 0 wiederholt sich.
Schreibweise: Wenn wir eine Fibonaccizahl Fn durch k dividieren, dann
schreiben wir für den Rest Kn.
Im Allgemeinen werden wir zeigen dass es eine Zahl m gibt so dass
Kim+j = Kj für alle i ≥ 0 und j ≥ 0.
Mit anderen Worten, wenn wir jede Fibonaccizahl durch k dividieren, dann erhalten wir die Reste:
K1,K2,...,Km,K1,K2,...
Das Muster K1,K2,...,Km wiederholt sich immer wieder.
Beweis:
(K1,K2), (K2,K3), (K3,K4), ..., (Kk2+1,Kk2+2) ist eine Folge von k2+1 Zahlenpaare.
Davon ist die Anzahl der verschiedenen Paare maximal k2, denn beide Koordinaten sind nicht größer als k-1.
Also gibt es in dieser Folge von Zahlenpaaren Doppeltexemplare. Sage, (Kp,Kp+1) = (Kq,Kq+1).
Wähle hierbei p und q möglichst klein (p<q). Wir zeigen jetzt dass p=1.
Kp = Kq
und deshalb ergeben Fp und Fq den gleichen Rest
wenn sie durch k dividiert werden, und genau so ergeben
Fp+1 und Fq+1 den gleichen Rest.
Aber dass bedeutet dass Fp-1 = Fp+1 - Fp und
Fq-1 = Fq+1 - Fq auch den gleichen Rest haben
und folglich ist Kp-1 = Kq-1 und
(Kp-1,Kp) = (Kq-1,Kq).
Das ist aber unmöglich, denn wir hatten für p und q die kleinsten Werte gewählt.
Offenbar ist (Kp-1,Kp)
kein Element der Zahlenpaarefolge, und das kann nur richtig sein wenn p = 1.
Deswegen ist p = 1. Für m können wir q-1 nehmen.
Wir haben gezeigt: Km+1 = K1 und Km+2 = K2.
Mit Induktion kann man nun einfach beweisen dass Km+j = Kj für alle j > 0.
Und daraus (wieder mit vollständiger Induktion) dass Kim+j = Kj für alle i ≥ 0 und j ≥ 0.