title: Stelling van Zeckendorf
text: 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 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
  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 .
  
  Getaltheorie
  Zeckendorf