Soorten getallen > Het dominoprincipe
123456Het dominoprincipe

Voorbeeld 1

Toon aan met het dominoprincipe:

Voor elke `n in NN` is `n^3-n` deelbaar door 3.

> antwoord

Gebruik de bewijsmethode van volledige inductie:

  • De kleinste `n` is `0` . Daarvoor klopt het, want `0^3-0=0` en dat is deelbaar door `3` .

  • Nu moet je aantonen:

    Als `n^3-n` deelbaar is door `3` , dan geldt ook:
    `(n+1)^3-(n+1)` is deelbaar door `3` .

    Dat gaat als volgt:

    Maak uit de uitdrukking `(n+1)^3-(n+1)` de uitdrukking `n^3-n` vrij:
    `(n+1)^3-(n+1)=n^3+3n^2+3n+1-n-1=n^3-n+3(n^2+n)`

    Bekijk nu het tweede deel van de uitdrukking: `3(n^2+n)` . Dat is deelbaar door `3` .

Conclusie:
Als `n^3-n` deelbaar is door `3 ` , dan is
`n^3-n+3(n^2+n)` deelbaar door `3` en omdat dat gelijk is aan
`(n+1)^3-(n+1)` , is dat ook deelbaar door `3` .

Omdat het vermoeden voor `n=0` klopt, klopt het dus voor alle `n in NN` .

Opgave 3

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 `18446744073709551615` graankorrels. Genoeg om heel India met een laag graan van 1 voet dikte te bedekken!"

a

Hoeveel graankorrels liggen er op de eerste vier vakjes van het schaakbord samen? Laat zien dat `1 +2 +4 +8 =2^4-1` .

b

Laat zien dat voor het aantal graankorrels op de eerste vijf vakjes samen geldt: `1 +2 +2^2+2^3+2^4=2^5-1` .

c

Het aantal graankorrels op de eerste vijf vakjes kun je ook afleiden door bij het totaal van de graankorrels op de eerste vier vakjes nog `2^4` op te tellen. Laat zien dat `2^4-1 +2^4=2^5-1` .

d

Bewijs met volledige inductie dat `1 + 2 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) - 1` als `n in NN` en `n>=1` .

e

Klopt het aantal graankorrels dat Sissa noemde?

Opgave 4

Bekijk een drietal beweringen.

  • `1 +1/2=2 -1/2`

  • `1 +1/2+1/4=2 -1/4`

  • `1 +1/2+1/4+1/8=2 -1/8`

Je kunt er regelmaat in ontdekken.

a

Ga na dat deze beweringen correct zijn.

b

Hoe zou de volgende bewering in deze serie luiden?

c

Formuleer een algemene regel en bewijs die regel met behulp van volledige inductie.

verder | terug