Dominoprincipe

Inleiding

Een belangrijke methode om stellingen te bewijzen die te maken hebben met de natuurlijke getallen is het zogenaamde "dominoprincipe". Gooi je de eerste steen om en staan alle stenen zo opgesteld dat elke steen zijn opvolger raakt als hij omvalt, dan vallen alle stenen om.
Hierop is de bewijsmethode van de volledige inductie gebaseerd.

Je leert nu:

de bewijsmethode van volledige inductie;
deze bewijsmethode toepassen.

Je kunt al:

rekenen met getallen in het tientallig stelsel;
haakjes uitwerken en ontbinden in factoren;
verschillende soorten bewijzen herkennen.

Verkennen

Over de beroemde wiskundige Carl Friedrich Gauss (1777 - 1855) gaat het verhaal dat hij als 11-jarige de opdracht kreeg om de getallen 1 t/m 100 bij elkaar op te tellen in de veronderstelling dat hij daarmee wel even bezig zou zijn. Na enkele seconden te hebben nagedacht wist Gauss meteen het antwoord 5050. Hij bedacht ter plekke dat je deze getallen kunt optellen door de eerste en de laatste op te tellen en dan de uitkomst te vermenigvuldigen met het halve aantal getallen.

> Ga na, dat deze methode inderdaad juist is.
> In het algemeen geldt: 1 + 2 + 3 + ... + n = $\frac{1}{2}$ n(n + 1).
Bewijs dat hieruit volgt: 1 + 2 + 3 + ... + n + n + 1 = $\frac{1}{2}$ (n + 1)(n + 2).
> Je hebt nu bewezen dat als de stelling geldt voor een bepaalde n hij ook geldt voor zijn opvolger. Als je nu kunt bewijzen dat de stelling geldt voor bijvoorbeeld n = 2, dat geldt hij dus ook voor n = 3 en daarom ook weer voor n = 4, etc.
Kun je het bewijs afmaken?

Uitleg

In het algemeen geldt: 1 + 2 + 3 + ... + n = $\frac{1}{2}$ n(n + 1).

Dit kun je op een aantal manieren bewijzen. Een manier is de bewijsmethode van de volledige inductie. Je gebruikt dan het dominoprincipe:

(je gooit een eerste steen om)
de stelling geldt voor bijvoorbeeld n = 1 (voor een bepaalde n, vaak n = 1):
1 = $\frac{1}{2}$ · 1 ·(1 + 1) klopt.
(een omvallende steen raakt zijn opvolger die dan ook omvalt)
als de stelling voor een bepaalde n geldt, dan volgt daaruit dat hij voor n + 1 geldt:
Dit betekent dat je moet aantonen dat
1 + 2 + 3 + ... + n + n + 1 = $\frac{1}{2}$ (n + 1)(n + 2)
volgt uit 1 + 2 + 3 + ... + n = $\frac{1}{2}$ n(n + 1). Probeer maar eens...

‡

Opgaven

In de Uitleg wordt het dominoprincipe gebruikt om een stelling over natuurlijke getallen te bewijzen.
1. Wat wordt in dit verband bedoeld met het dominoprincipe?
2. In welke situaties kun je dit dominoprincipe in een bewijs gebruiken?
3. Laat zien, dat 1 + 2 + 3 + ... + n + n + 1 = $\frac{1}{2}$ (n + 1)(n + 2)
  volgt uit 1 + 2 + 3 + ... + n = $\frac{1}{2}$ n(n + 1).
4. Ga na, dat uit de bewezen formule volgt `1 + 2 + 3 + ... + 99 + 100 = 5050`.

Je kunt de stelling `1 + 2 + 3 + ... + n - 1 + n = 1/2 n (n + 1)` ook wel anders bewijzen.
Zet `1 + 2 + 3 + ... + n - 1 + n` en `n + n - 1 + ... + 3 + 2 + 1` maar eens onder elkaar en tel ze op.
Hoe gaat het bewijs dan verder?

Theorie

Beweringen waarin natuurlijke getallen (aantallen) een rol spelen kun je soms bewijzen met behulp van het dominoprincipe. Dit wordt ook wel de bewijsmethode van volledige inductie genoemd.
Het werkt als volgt:

Je bewijst dat de bewering waar in voor n = 1.
(De inductiebasis, je duwt de eerste steen om)

Je bewijst dat voor elke n ≥ 1 geldt: als de bewering waar is voor n dan volgt daaruit dat hij ook waar is voor n + 1.
(De inductiestap, je laat zien dat elke steen zo staat opgesteld dat hij omvalt als zijn voorganger omvalt.)

‡

Voorbeeld 1

Bewijs met volledige inductie dat 1 + 2 + 2² + 2³ + ... + 2ⁿ = 2^n + 1 – 1.

Antwoord

Je moet bewijzen: 2⁰ + 2¹ + 2² + 2³ + ... + 2ⁿ = 2^n + 1 – 1.

De stelling geldt voor n = 1:
2⁰ + 2¹ = 2^1 + 1 – 1 klopt inderdaad.

De stelling geldt voor n ⇒ de stelling geldt voor n + 1:
1 + 2 + 2² + 2³ + ... + 2ⁿ + 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.

‡

Voorbeeld 2

Het aantal delen waarin het vlak verdeeld wordt door n lijnen die elkaar twee aan twee snijden en waarvan er geen drie door één punt gaan, is $\frac{1}{2}$ (n² + n + 2).

Antwoord

Teken dit om in te zien dat het toevoegen van de lijn met nummer n betekent dat er precies n – 1 snijpunten en precies n nieuwe delen bijkomen.
Gebruik verder het dominoprincipe:

Voor n = 1 klopt de stelling:
met 1 lijn zijn er $\frac{1}{2}$ (1² + 1 + 2) = 2 delen.

De stelling geldt voor n ⇒ de stelling geldt voor n + 1:
Bij n lijnen zijn er $\frac{1}{2}$ (n² + n + 2) delen.
Voeg je de lijn met nummer n + 1 toe, dan komen er ook n + 1 nieuwe delen bij.
Bij n + 1 zijn er dus $\frac{1}{2}$ (n² + n + 2) + n + 1 = $\frac{1}{2}$ ((n + 1)² + (n + 1) + 2) delen.

Q.e.d.

‡

Opgaven

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 `1 + 2 + 4 + 8 = 2^4 - 1`.
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`.
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 `2^4` op te tellen. Laat zien dat `2^4 - 1 + 2^4 = 2^5 - 1`.

In Voorbeeld 1 wordt met behulp van volledige inductie bewezen dat `1 + 2 + 2^2 + 2^3 + ... + 2^n = 2^(n+1) - 1`.

Voer zelf dit bewijs uit.
Voor welke waarde van `n` gaat deze stelling over het verhaal van Sissa? Klopt het aantal graankorrels dat hij noemde?

Je ziet hier 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.
1. Ga na dat de beweringen hierboven correct zijn.
2. Hoe zou de volgende bewering in deze serie luiden?
3. Formuleer een algemene regel en bewijs die regel met behulp van volledige inductie.

In Voorbeeld 2 wordt het principe van volledige inductie toegepast op een meetkundig probleem.
1. Laat met behulp van één of meer tekeningen zien dat de stelling geldt voor `n = 2`.
2. Laat met behulp van één of meer tekeningen zien dat de stelling geldt voor `n = 3`.
3. Waarom is het nodig dat er geen drie lijnen door één punt gaan?
4. Voeg aan je figuur (of figuren) een vierde lijn toe. Hoeveel vlakdelen komen er dan bij?
5. Waarom komen er bij de `(n + 1)`de lijn `n+1` vlakdelen bij?
6. Loop nu zelf het bewijs van de stelling na.

Teken je op een cirkel `n` punten op gelijke afstanden van elkaar, dan zijn dat hoekpunten van een regelmatige `n`-hoek. Het gaat om het aantal lichaamsdiagonalen van zo'n regelmatige `n`-hoek.
1. Neem `n = 3`. Hoeveel diagonalen zijn er?
2. Neem `n = 4`. Hoeveel diagonalen zijn er nu?
3. Neem `n = 5`. Hoeveel diagonalen zijn er in dit geval?
4. Laat zien dat het aantal diagonalen bij `n = 6` gelijk is aan `1/2 * 6 * 5 - 6`.
5. Bewijs met behulp van de dominopricipe dat het aantal diagonalen bij `n` gelijk is aan `1/2 * n * (n - 1) - n`.

Verwerken

Je ziet hier een drietal beweringen:
- `1 - 1/2 = 1/2`
- `(1 - 1/2)(1 - 1/3) = 1/3`
- `(1 - 1/2)(1 - 1/3)(1 - 1/4) = 1/4`
Je kunt er regelmaat in ontdekken.
1. Ga na dat de beweringen hierboven correct zijn.
2. Hoe zou de volgende bewering in deze serie luiden?
3. Formuleer een algemene regel en bewijs die regel met behulp van volledige inductie.

Bewijs met volledige inductie dat `1 + 2^2 + 3^2 + 4^2 + ... + n^2 = 1/6 n(n + 1)(2n + 1)`.

Bewijs met behulp van volledige inductie dat `n^2 + n` een even getal is voor alle `n in NN`.

Uit de Griekse Oudheid stamt de stelling:

Als je een lijnstuk van lengte 1 gegeven hebt, kun je met een passer en een liniaal een lijnstuk met een lengte `sqrt(n)` met `n` een natuurlijk getal construeren.
1. Laat zien dat dit waar is voor `n = 2`. (Denk er om dat je alleen liniaal en passer gebruikt, geen gradenboog!)
2. Laat zien, dat uit het lijnstuk met lengte 1 en dat met lengte `sqrt(2)` een lijnstuk met lengte `sqrt(3)` is te construeren.
3. Bewijs nu de stelling.

Testen

Bewijs met volledige inductie dat `1 + 2^3 + 3^3 + 4^3 + ... + n^3 = 1/4 n^2(n + 1)^2`.

Bewijs met behulp van het dominoprincipe dat de som van de hoeken van een `n`-hoek met hoeken kleiner dan 180° gelijk is aan `(n - 2) * 180`. Waarom is het nodig dat alle hoeken kleiner dan 180° zijn?