Fibonacci

Patroonherhaling:

We hebben gezien, dat als we elk Fibonaccigetal door 4 delen, we de volgende resten krijgen:
1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, 1, 1, 2, 3, 1, 0, ...
Het patroon 1, 1, 2, 3, 1, 0 blijft zich herhalen.
Notatie: Als we een Fibonaccigetal F_n door k delen, dan geven we de rest aan met K_n.

In het algemeen zullen we aantonen dat er een getal m bestaat zo dat K_im+j = K_j voor alle i ≥ 0 en j ≥ 0.
M.a.w., als we elk Fibonaccigetal door k delen, dan krijgen we de resten:
K₁,K₂,...,K_m,K₁,K₂,...
Het patroon K₁,K₂,...,K_m blijft zich herhalen.
Bewijs:
(K₁,K₂), (K₂,K₃), (K₃,K₄), ..., (K_k²+1,K_k²+2) is een rijtje van k²+1 getallenparen.
Hiervan is het aantal verschillende paren maximaal k², want beide coordinaten kunnen niet groter zijn dan k-1.
Dus in dit rijtje getallenparen bevinden zich dubbelen. Zeg, (K_p,K_p+1) = (K_q,K_q+1).
Kies hierbij p en q zo klein mogelijk (p<q). We tonen nu aan dat p=1.
K_p = K_q en dus geven F_p en F_q dezelfde rest bij deling door k, en evenzo F_p+1 en F_q+1 geven dezelfde rest bij deling door k.
Maar dat houdt in dat F_p-1 = F_p+1 - F_p en F_q-1 = F_q+1 - F_q ook dezelfde rest even bij deling door k en dus is K_p-1 = K_q-1 en (K_p-1,K_p) = (K_q-1,K_q).
Dit kan niet, want we hadden voor p en q de kleinste waarden genomen. Blijkbaar is (K_p-1,K_p) geen element van het rijtje getallenparen, en dat kan alleen als p = 1.
Derhalve is p = 1. Voor m kunnen we deze q-1 nemen.
We hebben bewezen: K_m+1 = K₁ en K_m+2 = K₂.
Met inductie is dan eenvoudig te bewijzen dat K_m+j = K_j voor alle j > 0.
En hieruit (weer met volledige inductie) dat K_im+j = K_j voor alle i ≥ 0 en j ≥ 0.