Soorten getallen > Het dominoprincipeVoorbeeld 1
Bewijs met volledige inductie dat `1 + 2 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) - 1` .
Je moet bewijzen: `2^0 + 2^1 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) - 1` .
-
De stelling geldt voor `n=1` :
`2^0 + 2^1 = 2^1 + 1 - 1` klopt inderdaad. -
De stelling geldt voor `=>` de stelling geldt voor `n + 1` :
`1 + 2 + 2^2 + 2^3 + ... + 2^n + 2^(n+1) = 2^(n+1) - 1 + 2^(n+1) =`
`= 2 * 2^(n+1) - 1 = 2^(n+2) - 1` .
Dus inderdaad volgt uit de stelling geldt voor `n` , dat de stelling ook voor `n + 1` geldt.
Q.e.d.
Uit "Merkwaardige en interessante raadsels en puzzels" van David Wells:
| Ene Ibn Kallikan (omstreeks 1256) heeft het verhaal van Sissa ben Dahir opgetekend. Voor de uitvinding van het schaakspel vroeg Sissa aan de Indiase koning Shirham de hoeveelheid graan die verzameld zou worden als men op het eerste veld van het schaakbord één graankorrel zou leggen, op het tweede het dubbele aantal, op het derde weer het dubbele tot en met het 64e veld. De koning zei: "En is dat alles wat je hebben wilt, Sissa, jij dwaas? Je krijgt het meteen mee!". Maar Sissa zei: "Vergis u niet, dit zijn in totaal 18.446.744.073.709.551.615 graankorrels. Genoeg om heel India met een laag graan van 1 voet dikte te bedekken!" |
Hoeveel graankorrels liggen er op de eerste vier vakjes van het schaakbord samen? Laat zien dat .
Laat zien dat voor het aantal graankorrels op de eerste vijf vakjes samen geldt: .
Het aantal graankorrels op de eerst vijf vakjes kun je ook afleiden door bij het totaal van de graankorrels op de eerste vier vakjes nog op te tellen. Laat zien dat .
In
Voer zelf dit bewijs uit.
Voor welke waarde van gaat deze stelling over het verhaal van Sissa? Klopt het aantal graankorrels dat hij noemde?
Je ziet hier een drietal beweringen:
Je kunt er regelmaat in ontdekken.
Ga na dat de beweringen hierboven correct zijn.
Hoe zou de volgende bewering in deze serie luiden?
Formuleer een algemene regel en bewijs die regel met behulp van volledige inductie.