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 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\ge 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. De voorwaarde c_i\ge 2 voorkomt dat het getal 3 twee representaties zou hebben, namelijk zichzelf en f_1+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[bewerken]

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 \le n de uitspraak geldig is.

Inductiestap

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

f_i < n +1\le 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 \ne 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.