Fibonacci

Bewijs:

We willen aantonen dat elk getal geschreven kan worden als som van verschillende Fibonaccigetallen, waarvan elk tweetal indices minstens 2 verschillen.
Uit het ongerijmde. M.a.w.:
Stel de stelling is onjuist, d.w.z. er is een getal N waarvoor geldt:
Als N = F_i1 + F_i2 + ... + F_ik dan is i_r - i_s = 1 voor zekere r en s.
We zullen in dit geval i_s een duwindex noemen.
We veronderstellen dus dat elke representatie van N minstens 1 duwindex heeft.
B is de verzameling van representaties van N met een kleinst mogelijk aantal duwindices.
Kies nu uit deze verzameling een representatie met de grootst mogelijke duwindex.
Zeg N = F_j1 + F_j2 + ... + F_jm en j_u is de grootste duwindex.
Dan zijn F_ju en F_ju+1 sommanden in deze representatie en F_ju+2 niet.
Vervang nu in deze representatie de 2 sommanden F_ju en F_ju+1 door F_ju+2.
Stel F_ju+3 is een sommand in de nieuwe representatie. Dan is deze representatie ook een element van B! Echter, dan is j_u+2 een duwindex. Maar dat kan niet, want j_u is de grootst mogelijke.
Dus F_ju+3 is geen sommand in de nieuwe representatie. Maar dat kan ook niet, omdat we dan een representatie hebben met een aantal duwindices dat 1 kleiner is dan het minimale aantal.
Dus de veronderstelling dat N minstens 1 duwindex heeft kan niet juist zijn, en daarmee is de stelling bewezen.