Stelling van Zeckendorf

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Weergave Zeckendorfrepresentaties met 144, 89, 55, 34, 21, 13, 8, 5, 3, 2 en 1 uit de rij van Fibonacci

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 , enzovoort. Preciezer geformuleerd luidt de stelling: als een positief geheel getal is, zijn er positieve gehele getallen , met , zodat

waar het n-de getal uit de rij van Fibonacci is. Met de voorwaarde elemineert men de eerste 1, wat noodzakelijk is voor de eenduidigheid van de de som. De voorwaarde is noodzakelijk omdat anders het getal 3 twee representaties zou hebben, namelijk en .

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[bewerken]

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

Inductiebegin

Voor en is de uitspraak geldig, want en zijn beide zelf Fibonacci-getallen.

Inductieveronderstelling

Stel dat voor alle getallen de uitspraak geldig is.

Inductiestap

Er zijn twee opeenvolgende Fibonacci-getallen en , zodanig dat:

.

Als geldt de uitspraak voor . We kijken dus nog naar het geval dat:

.

of anders geschreven:

.

Omdat , is ook , en geldt volgens de inductiveronderstelling voor dat er een som van niet-opeenvolgende Fibonacci-getallen is, met:

.

Omdat , komt niet voor in de som , en is 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 als grootste getal, is kleiner dan het volgende Fibonacci-getal .

Het lemma kan met inductie bewezen worden.

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

en .

Dan hebben ook en dezelfde som.

Veronderstel dat beide verzamelingen en niet leeg zijn en laat en de grootste elementen zijn van respectievelijk en . Omdat en geen gemeenschappelijke elementen bevatten, is . Voor het gemak nemen we aan dat .

Volgens het lemma is de som van de elementen uit kleiner dan , en dus ook kleiner dan . De som van de elementen uit is echter ten minste gelijk aan . Dit is in tegenspraak met het feit dat en dezelfde som hebben. Dus moet een van beide verzamelingen leeg zijn. Maar dan is ook de andere leeg, en is .