Bewijs:
Uit het vorige bewijs weten we, dat het aantal enen in het beginstuk van lengte k van het rijtje 1 0 1 1 0 1 0 1 1 0 1 1 ... gelijk is aan [(k+1)/
].We zullen nu aantonen dat het aantal nullen in het beginstuk van lengte k gelijk is aan S(k) = [(k+1)/
2].We willen dus aantonen dat [(k+1)/
] + [(k+1)/2] = k.[(k+1)/
] + [(k+1)/2] =[(k+1)(
-1)] + [(k+1)(2-)] =[(k+1)
] - (k + 1) + 2(k + 1) - [(k+1)] - 1 = k.Het k-de element van het rijtje is nul, precies dan als S(k) - S(k-1) = 1.
We zullen nu aantonen dat S(k) - S(k-1) = 1 precies dan als k te schrijven is als [n
2] voor zeker geheel getal n.S(k) - S(k-1) = [(k+1)/
2] - [k/2].S(k) - S(k-1) = 1 dan en slechts dan als [k/
2] < [(k+1)/2]ofwel als er een geheel getal m bestaat zo, dat k/
2 < m < (k+1)/2, dit is als k < m2 < k+1,ofwel als k te schrijven is als [m
2].
We hebben nu aangetoond dat elk natuurlijk getal geschreven kan worden òf als [k
], òf als [k2].Als an = [n
], dan is bn = an + n = [n] + n = [n( + 1)] = [n2].We tonen nog even aan dat an = [n
] voor elke n.Uit de definitie volgt onmiddellijk dat het rijtje a1, b1, a2, b2, ... een stijgend rijtje moet zijn.
(Met verloopsinductie) a1 = [1.
]. Stel ak = [k] voor k<K.Nu is aK = [m
], met m = K (omdat aK het kleinste getal is dat nog niet is opgetreden in de rij), òf
aK = [m2] voor zekere m.In dat laatste geval is [m
] kleiner dan [m2], dus (inductie hypothese) [m] = am voor zekere m < K,
en bm = [m2]. Blijkbaar kwam [m2] al eerder in het rijtje voor, hetgeen tegenstrijdig is met de regels.Conclusie: ak = [k
] voor elke k.Verder:
2 = + 1, dus n2 = n + n en [n2] = [n] + n.
Kortom, elk natuurlijk getal kan geschreven worden als [n2] - [n] voor zekere n.Ik toon aan dat F2n = [F2n-1
].F2n-1 = (r2n-1 - s2n-1)/(r - s), met r =
en rs = -1.Dan is F2n-1
= (r2n + s2(n-1))/(r - s) > (r2n - s2n)/(r - s) = F2n en(r2n + s2(n-1))/(r - s) - (r2n - s2n)/(r - s) = (1/r2(n-1) + 1/r2n)/
5 < 1. Dus F2n = [F2n-1
].Dan is [F2n-1
2] = [F2n-1] + F2n-1 = F2n + F2n-1 = F2n+1Elke Fn met even n is dus een ak, dus elke Fn met oneven n is een bk. Een analoog verhaal geldt voor Lucasgetallen.