Met n! geven we het product nx(n-1)...2x1 aan. Toon aan dat ieder natuurlijk getal ¹0 op unieke wijze te schrijven is als c1 x 1! + c2 x 2! + c3 x 3! +...+ cn x n! waarbij voor i=1,...,n het getal ci een natuurlijk getal kleiner of gelijk aan i is, en cn¹0.
Kweet nie hoek di moe doen!
Anna S
Student hbo - zondag 21 september 2003
Antwoord
Laten we afspreken een Cantor-getal van m cijfers te noteren als [cm,...,c1]. Aan de opgelegde voorwaarden voor de coefficienten kan je zien dat er zo (m+1)! getallen kunnen gevormd worden, wanneer we [0,..,0] voor de handigheid meerekenen.
Veronderstelle we nu dat die m! Cantor-getallen inderdaad de natuurlijke getallen van 0 tot en met (m+1)!-1 voorstellen. Door toevoeging van een (m+1)-ste cijfer aan alle m-cijferige Cantor-getallen kunnen we dan de getallen
De eerste rij getallen komt overeen met de m-cijferige Cantor-getallen die we al hadden, de overige ontstaan door het toevoegen van een van nul verschillend nieuw cijfer. Je ziet zelf dat het einde van een rij en het begin van de volgende rij mooi aansluiten. Het laatste getal van de laatste rij is (m+1)(m+1)!+(m+1)!-1 = (m+1)!(m+2) - 1 = (m+2)!-1. We hebben dus op die manier alle getallen voorgesteld van 0 tot en met (m+2)!-1.
Dit procede kunnen we dan herhalen om te bewijzen dat we met n-cijferige Cantor-getallen alle natuurlijke getallen van 0 tot en met (n+1)!-1 uniek kunnen voorstellen.
We hebben wel nog iets nodig om onze inductie mee te beginnen en dat kan bijvoorbeeld het geval m=1 zijn. We kunnen verifieren dat [0]=0 en [1]=1 is en dat inderdaad alle getallen van 0 tot en met (m+1)!-1=1 uniek kunnen worden voorgesteld. En zo kan de inductie zijn werk doen!
