Unieke Fibonacci-som

[efdee]

De stelling van Zeckendorf
Ieder telgetal is òf een Fibonacci-getal òf de som van een aantal elkaar niet opvolgende Fibonacci-getallen.
Zo’n som is uniek.

Bijvoorbeeld 100 = 3 + 8 + 89 en 64 = 55 + 8 + 1.
Volgens welk 'recept' vind je die unieke som?

[Xilvo]

Dat recept lijkt me (zonder het te bewijzen) eenvoudig:
Het getal x is een Fibonaccigetal; klaar.
Zo niet: vind het grootste Fibonaccigetal < x, trek dat van x af.
Herhaal tot je op een Fibonaccigetal komt.

[efdee]

Zie de cursief gedrukte tekst.

[Xilvo]

Zie de cursief gedrukte tekst.

Gezien. Ik gaf een methode om de getallen te vinden, geen bewijs voor de stelling.

[RedCat]

Zie de cursief gedrukte tekst (= "elkaar niet opvolgende Fibonacci-getallen")

Zie het recept van Xilvo.

Als x zelf geen Fibonacci-getal is, dan ligt x tussen 2 opeenvolgende Fibonacci-getallen in:

\(\small f_{n-1} < x < f_n\)

Trek het grootste Fibonacci-getal kleiner dan x hiervan af:

\(\small (f_{n-1}-f_{n-1}) < (x-f_{n-1}) < (f_n-f_{n-1})\)

ofwel

\(\small 0 < (x-f_{n-1}) < f_{n-2}\)

Het volgende Fibonacci-getal in de Zeckendorf-representatie van x is dus kleiner dan f_n-2 (= de voorganger van f_n-1).

Construeer hiermee een inductief bewijs voor het bestaan van zo'n representatie.

[efdee]

Het ging me niet om een bewijs van de stelling maar om de manier waarop je de termen van zo'n som kunt bepalen.

[Xilvo]

Het ging me niet om een bewijs van de stelling maar om de manier waarop je de termen van zo'n som kunt bepalen.

Die gaf ik, en toen vroeg je naar het bewijs. Wat RedCat vervolgens deed.