Reizen door de natuurlijke getallen (2).
Laat ak het aantal getallen op afstand k van 1 zijn. Dan is
ak = 1 voor k < 3. Neem nu k groter of gelijk aan 3. Twee of
meer keer -1 na elkaar geeft een getal dat al eerder voorkomt, dus na -1 komt
alleen ×2.
Gevolg: alle even getallen ontstaan uit ×2 en alle
oneven getallen ontstaan uit -1 (uitgaande van een even getal). Op niveau k-1
worden alle getallen verdubbeld; dit geeft ak-1 even getallen op
niveau k. De even getallen op niveau k-1 (dat zijn er dus ak-2)
worden met 1 verminderd; dat geeft ak-2 oneven getallen op niveau k.
In totaal zijn er dus ak-1 + ak-2 verschillende getallen
op niveau k.
Om te kunnen concluderen dat ak = ak-1 + ak-2, moeten we nog aantonen dat er geen getallen ontstaan die eerder zijn gevormd. Welnu, stel getal g staat op niveau p en op niveau q met p < q en p minimaal. Dit leidt al snel tot een tegenspraak.
Aanvulling op de kalender: "... gelijk aan b+g ..." moet zijn: "... minstens gelijk aan b+g ...".
We gebruiken de notatie b(n) voor het aantal bits van n en g(n) voor het aantal rijtjes opvolgende enen in de tweetallige representatie van n.