Stelling van Zeckendorf

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

Weergave Zeckendorfrepresentaties met 144, 89, 55, 34, 21, 13, 8, 5, 3, 2 en 1 uit de rij van Fibonacci

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 $f_{1}=1,f_{2}=1,f_{3}=2,f_{4}=3$, enzovoort. Preciezer geformuleerd luidt de stelling: als $n$ een positief geheel getal is, zijn er positieve gehele getallen $c_{i}\geq 2$, met $c_{i+1}>c_{i}+1$, zodat

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

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

Bewijs van de stelling

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

Inductiebegin

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

Inductieveronderstelling

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

Inductiestap

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

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

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

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

of anders geschreven:

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

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

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

Omdat $S=n+1-f_{i}<f_{i-1}$, komt $f_{i-1}$ niet voor in de som $S$, en is $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 $f_{m}$ als grootste getal, is kleiner dan het volgende Fibonacci-getal $f_{m+1}$.

Het lemma kan met inductie bewezen worden.

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

$U'=U\setminus V$ en $V'=V\setminus U$.

Dan hebben ook $U'$ en $V'$ dezelfde som.

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

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