Pythagoras augustus 1999

Het domino-principe

door André de Boer

Wat heeft het wereldrecord dominostenen omgooien met wiskunde te maken? Het antwoord op deze vraag luidt: `het domino-principe'. Dit is een krachtige techniek waarmee je allerlei wiskundige uitspraken kunt bewijzen.

Het wereldrecord dominostenen omtuimelen staat op 1,4 miljoen stenen. Het werd gevestigd op 28 augustus vorig jaar in Leeuwarden. Je hebt het misschien wel gezien op tv: een grote hal met een vloeroppervlak van 4000 m² waarin een lint van 78 km dominostenen was uitgezet. In totaal waren er 2,3 miljoen stenen geplaatst. Op een gegeven moment kreeg de eerste steen een duwtje, deze viel om en gaf de tweede steen een duwtje, zodat deze omviel en waardoor ook de derde steen omviel ... enzovoort. Uiteindelijk vielen er 1,4 miljoen stenen om; net voldoende om het wereldrecord te vestigen en opgenomen te worden in het Guiness Book of Records.

Bewijzen

Stel je wilt bewijzen dat de som van de eerste n getallen gelijk is aan $\smfrac{1}{2}n(n+1)$ . Met andere woorden, je wilt bewijzen dat:

$\begin{displaymath}\vcenter{\openup1\jot\halign{\hfil${} ...$

en ga zo maar door. In een formule:

$\begin{displaymath}1+2+3+\cdots+n=\smfrac{1}{2}n(n+1). \end{displaymath}$

Je kunt controleren dat de formule klopt voor 1, 2 en 3.

Stel nu eens dat je wil bewijzen dat deze formule klopt voor alle natuurlijke getallen 1, 2, 3, 4, ... Als je de formule eerst controleert voor 1, daarna voor 2, dan voor 3, dan voor 4, voor 5, voor 6, dan begrijp je dat het bewijs nooit afkomt. Ga maar na: stel dat je vanaf je achttiende tot je achtenzeventigste levensjaar elke dag acht uur aan dit bewijs werkt. Als je 1 minuut nodig hebt om de formule voor één getal te controleren, dan zal je bij je overlijden niet verder zijn dan het getal:

$\begin{displaymath}60\times 365\smfrac14\times 8\times 60 = 10.519.200. \end{displaymath}$

In deze berekening staat $365\smfrac14$ omdat eens in de vier jaar een jaar 366 dagen telt. Je ziet dat je dan nog lang niet klaar bent. Zelfs de snelste computer zal het bewijs nooit af krijgen, eenvoudig omdat er te veel getallen zijn.

Volledige inductie

Er bestaat een techniek die het mogelijk maakt de formule in één klap voor alle getallen tegelijk te bewijzen. Deze techniek wordt natuurlijke of volledige inductie genoemd en doet met getallen hetzelfde als met de domino-stenen gebeurde.

Voor deze methode hoef je de formule maar voor één geval te controleren, namelijk voor n=1. Verder moet je het domino-effect aantonen. Dit houdt in dat je van een bewijs van de formule voor een bepaald getal een bewijs kunt maken voor het volgende getal.

Het bewijs van de formule voor een bepaald getal kun je je voorstellen als een omgevallen dominosteen. Het domino-effect garandeert dat als de formule voor een bepaald getal `omgevallen is', de formule ook `omvalt' voor het volgende getal.

Als je n=1 gecontroleerd hebt, heb je de eerste steen omgegooid. Met het domino-effect volgt dan ook de tweede steen, de derde steen, enzovoort. Het domino-effect zorgt er voor dat als de formule `omgevallen is' voor het lint van alle getallen tot en met de n-de steen, de formule ook omvalt voor de (n+1)-ste steen. Zodoende weet je dan zeker dat de formule `omvalt' voor alle getallen.

Een voorbeeld

Met volledige inductie gaan we de volgende formule voor $1+2+3+\cdots+n$ bewijzen:

$\begin{displaymath}1+2+3+\cdots+n=\smfrac{1}{2}n(n+1). \end{displaymath}$

Daarvoor moeten we twee dingen doen:
1. de formule bewijzen voor n=1;
2. het domino-effect aantonen.

Het bewijs

1. Voor n=1 is de formule eenvoudig:

$\begin{displaymath}1=\smfrac{1}{2}\cdot(1+1) \end{displaymath}$

De eerste steen is omgekukeld.

2. In de volgende stap van het bewijs moeten we aantonen dat als de formule waar is voor het getal n, de formule ook waar is voor het volgende getal n+1. Stel dus dat de formule klopt voor het getal n. Men noemt deze veronderstelling de inductieveronderstelling:

$\begin{displaymath}1+2+3+\cdots+n=\smfrac{1}{2}n(n+1). \end{displaymath}$

Let op: de formule geldt hier voor slechts één bepaalde n (en niet voor alle n). Nu volgt:

$\begin{displaymath}\vcenter{\openup1\jot\halign{\hfil${} ...$

Hier staat de formule die we wilden bewijzen, alleen staat nu op de plaats van de n het getal n+1. Met andere woorden: als de formule opgaat voor n, dan gaat hij ook op voor n+1.

Omdat we de formule waar is voor n=1, is hij nu ook waar voor n=2. En omdat hij waar is voor n=2, is hij ook waar voor n=3. En daarom ook voor n=4, enzovoort. Met behulp van het domino-principe volgt dus dat de formule waar is voor alle getallen 1, 2, 3, 4, ...

OPGAVEN. 1. Laat met volledige inductie zien dat voor alle $n=1,2,3,\ldots$ de volgende formule waar is:

$\begin{displaymath}1^3+2^3+\dots+n^3=\smfrac{1}{4}n^2(n+1)^2. \end{displaymath}$

2. Bewijs voor alle $n=1,2,3,\ldots$

3²ⁿ⁺¹+2^n-1 is deelbaar door 7.

De bewijzen kun je onderaan deze Internetpagina vinden.

Johann Carl Friedrich Gauss
Het domino-effect is niet de enige wiskundige bewijstechniek. Zo gaat het verhaal dat de jonge Gauss op school als strafwerk een keer de eerste 100 getallen bij elkaar op moest tellen. Binnen enkele seconden had hij al de uitkomst bepaald. Hoe deed hij dat? Hij telde het eerste getal uit $1+2+3+\cdots+100$ bij het laatste getal op, het tweede getal bij het één na laatste getal en zo verder:

$\begin{eqnarray*}1+100&=&101\\ 2+99&=&101\\ 3+98&=&101\\ \cdots \\ 50+51&=&101 \end{eqnarray*}$

Er staat nu 50 keer de uitkomst 101, dus het antwoord luidt:

$\begin{displaymath}50\times 101=5050. \end{displaymath}$

Deze methode bewijst voor n=100 zónder volledige inductie de formule $1+2+3+\cdots+n=\smfrac12n(n+1)$ , immers: $50=\smfrac{1}{2}\times n$ en 101=n+1.

Oplossingen van de opgaven

Opgave 1. In de eerste opgave moeten we aantonen dat voor alle $n=1,2,3,\dots$ de volgende formule geldt:

$\begin{displaymath}1^3+2^3+\cdots +n^3=\frac{1}{4}n^2(n+1)^2. \end{displaymath}$

Voor n=1 is de formule eenvoudig:

1³=1

$\begin{displaymath}\frac{1}{4}\cdot 1^2 \cdot (1+1)^2=\frac{1}{4}\cdot 1\cdot 2^2=\frac{1}{4}\cdot 4=1\end{displaymath}$

Nu de inductiestap. Stel dat de formule waar is voor n. Dan tonen we nu dat ie ook waar is voor n+1.

$\begin{eqnarray*}1^3&+&2^3+\cdots +n^3+(n+1)^3 \\ & = & \frac{1}{4}n^2(n+1)^2+(... ... & (n+1)^2\frac{1}{4}(n+2)^2 \\ & = & \frac{1}{4}(n+1)^2(n+2)^2 \end{eqnarray*}$

In de tweede stap hebben we gebruik gemaakt van de inductieveronderstelling. Omdat de formule waar is voor n=1 en de inductiestap ook bewezen is, geldt de formule voor alle n.

Opgave 2. In de tweede opgave moeten we aantonen dat voor alle $n=1,2,3,\dots$ geldt:

$\begin{displaymath}3^{2n+1}+2^{n-1} \rm {\ deelbaar~is~door~7}. \end{displaymath}$

Stel n=1 dan volgt:

$\begin{displaymath}3^{2\cdot 1 +1}+2^{1-1}=3^3+2^0=27+1=28 \end{displaymath}$

$\begin{displaymath}28=4\cdot 7 \end{displaymath}$

Dus voor n=1 is de bewering waar.

Nu de inductiestap. Stel dat de formule waar is voor n. Dan tonen we nu dat ie ook waar is voor n+1.

$\begin{eqnarray*}3^{2(n+1)+1}&=&2^{(n+1)-1} \\ & = & 3^{2n+2+1}+2^{n+1-1}\\ & ... ...{n-1} \\ & = & 7\cdot 3^{2n+1} + 2\cdot (3^{2n+1} + 2^{n-1})\\ \end{eqnarray*}$

De eerste term van de laatste uitdrukking is deelbaar door 7, de andere term van die uitdrukking is volgens de inductieveronderstelling ook deelbaar door 7. Maar dan is de laatste uitdrukking en daarmee dus ook de eerste deelbaar door 7. Dus de formule geldt ook voor n+1.

Omdat de formule waar is voor n=1 en de inductiestap ook bewezen is, geldt de formule van opgave 2 voor alle n.
Warning: setlocale() [function.setlocale]: Passing locale category name as string is deprecated. Use the LC_* -constants instead in /websites/users/pyth/public_html/pythwww/common/footer.php on line 5

Laatst bijgewerkt op: Tuesday 27 May 2003, 14:10