Stelling van Zeckendorf

De stelling van Zeckendorf is een wiskundige stelling uit de getaltheorie.

De stelling zegt dat ieder positief geheel getal op unieke wijze geschreven kan worden als de som van een of meer elkaar niet opvolgende getallen uit de rij van Fibonacci. Anders dan in het artikel over de rij van Fibonacci begint de rij voor toepassing van de stelling met ${\displaystyle f_{1}=1,f_{2}=1,f_{3}=2,f_{4}=3}$, enzovoort. Preciezer geformuleerd luidt de stelling: als ${\displaystyle n}$ een positief geheel getal is, zijn er positieve gehele getallen ${\displaystyle c_{i}\geq 2}$, met ${\displaystyle c_{i+1}>c_{i}+1}$, zodat

${\displaystyle n=\sum _{i=0}^{k}f_{c_{i}},}$

waar ${\displaystyle f_{n}}$ het n-de getal uit de rij van Fibonacci is. Met de voorwaarde ${\displaystyle c_{i}\geq 2}$ elemineert men de eerste 1, wat noodzakelijk is voor de eenduidigheid van de som. De voorwaarde ${\displaystyle c_{i+1}>c_{i}+1}$ is noodzakelijk omdat anders het getal 3 twee representaties zou hebben, namelijk ${\displaystyle f_{4}}$ en ${\displaystyle f_{2}+f_{3}}$.

Een dergelijke som wordt de Zeckendorfrepresentatie van een getal genoemd.

De Zeckendorfrepresentatie van 100 is

100 = 3 + 8 + 89.

Andere manieren om 100 als som van getallen uit de rij van Fibonacci te schrijven voldoen niet. Bijvoorbeeld

100 = 1 + 2 + 8 + 89

100 = 3 + 8 + 34 + 55

hebben 1 en 2, respectievelijk 34 en 55, als paar van opeenvolgende getallen uit de rij van Fibonacci.

De stelling van Zeckendorf is vernoemd naar de Belgische wiskundige Edouard Zeckendorf.

We bewijzen eerst het bestaan van een Zeckendorfrepresentatie voor elk positief geheel getal ${\displaystyle n}$, en wel met volledige inductie naar ${\displaystyle n}$.

Inductiebegin

Voor ${\displaystyle n=1}$ en ${\displaystyle n=2}$ is de uitspraak geldig, want ${\displaystyle 1=f_{1}}$ en ${\displaystyle 2=f_{3}}$ zijn beide zelf Fibonacci-getallen.

Inductieveronderstelling

Stel dat voor alle getallen ${\displaystyle 0<m\leq n}$ de uitspraak geldig is.

Inductiestap

Er zijn twee opeenvolgende Fibonacci-getallen ${\displaystyle f_{i}}$ en ${\displaystyle f_{i+1}}$, zodanig dat:

${\displaystyle f_{i}<n+1\leq f_{i+1}}$.

Als ${\displaystyle n+1=f_{i+1}}$ geldt de uitspraak voor ${\displaystyle n+1}$. We kijken dus nog naar het geval dat:

${\displaystyle f_{i}<n+1<f_{i+1}}$.

of anders geschreven:

${\displaystyle 0<n+1-f_{i}<f_{i+1}-f_{i}=f_{i-1}}$.

Omdat ${\displaystyle f_{i-1}<n}$, is ook ${\displaystyle n+1-f_{i}<n}$, en geldt volgens de inductiveronderstelling voor ${\displaystyle n+1-f_{i}}$ dat er een som ${\displaystyle S}$ van niet-opeenvolgende Fibonacci-getallen is, met:

${\displaystyle S=n+1-f_{i}}$.

Omdat ${\displaystyle S=n+1-f_{i}<f_{i-1}}$, komt ${\displaystyle f_{i-1}}$ niet voor in de som ${\displaystyle S}$, en is ${\displaystyle n+1=S+f_{i}}$ dus ook een som van niet-opeenvolgende Fibonacci-getallen.

Vervolgens bewijzen we de eenduidigheid van de representatie. Daarvoor geven we eerst het volgende lemma.

Lemma

De som van elke niet-lege verzameling van verschillende, niet-opeenvolgende Fibonacci-getallen met ${\displaystyle f_{m}}$ als grootste getal, is kleiner dan het volgende Fibonacci-getal ${\displaystyle f_{m+1}}$.

Het lemma kan met inductie bewezen worden.

Veronderstel nu dat twee niet-lege verzamelingen ${\displaystyle U}$ en ${\displaystyle V}$ van verschillende, niet-opeenvolgende Fibonacci-getallen, dezelfde som hebben. Laat de gemeenschappelijke elementen weg uit beide verzamelingen:

${\displaystyle U'=U\setminus V}$ en ${\displaystyle V'=V\setminus U}$.

Dan hebben ook ${\displaystyle U'}$ en ${\displaystyle V'}$ dezelfde som.

Veronderstel dat beide verzamelingen ${\displaystyle U'}$ en ${\displaystyle V'}$ niet leeg zijn en laat ${\displaystyle f_{u}}$ en ${\displaystyle f_{v}}$ de grootste elementen zijn van respectievelijk ${\displaystyle U'}$ en ${\displaystyle V'}$. Omdat ${\displaystyle U'}$ en ${\displaystyle V'}$ geen gemeenschappelijke elementen bevatten, is ${\displaystyle f_{u}\neq f_{v}}$. Voor het gemak nemen we aan dat ${\displaystyle f_{u}<f_{v}}$.

Volgens het lemma is de som van de elementen uit ${\displaystyle U'}$ kleiner dan ${\displaystyle f_{u+1}}$, en dus ook kleiner dan ${\displaystyle f_{v}}$. De som van de elementen uit ${\displaystyle V'}$ is echter ten minste gelijk aan ${\displaystyle f_{v}}$. Dit is in tegenspraak met het feit dat ${\displaystyle U'}$ en ${\displaystyle V'}$ dezelfde som hebben. Dus moet een van beide verzamelingen leeg zijn. Maar dan is ook de andere leeg, en is ${\displaystyle U=V}$.