WisFaq!

Hoe werkt een bewijs met behulp van volledige inductie

Hoi,
Ik zag dat inductie al een aantal keer aan bod is gekomen, het is me al aardig duidelijk, maar ik heb nog een klein vraagje:

stel ik heb onderstaande tabel:
n a
1 1
2 4
3 9
4 16

De formule is n²
Hoe kan ik m.b.v. inductie controleren dat de formule voor iedere n klopt?

marijn van schoote
9-9-2003

Antwoord

Beste Marijn,

Je vraag
Hier is geen sprake van bewijzen met behulp van volledige inductie. n² 'definieert' de getallen in je tabel. Er valt dus niet echt iets te bewijzen. Eigenlijk alleen maar iets te controlleren.
Namelijk dat 1²=1, 2²=4, 3²=9 en 4²=16.

Volledige inductie
Je kunt volledige inductie gebruiken om een eigenschap van een oneindig aantal getallen te bewijzen.
Je hebt dus een oneindig aantal getallen gedefinieerd, waarvan je vermoedt dat ze een bepaalde eigenschap bezitten. Omdat het om een oneindig aantal getallen gaat, kun je de eigenschap niet voor elk getal afzonderlijk bewijzen en gebruik je volledige inductie om het voor allen te bewijzen.
Je gebruikt een soort domino effect. Je bewijst het voor 1 bepaald getal. Vervolgens bewijs je dat als een getal aan de eigenschap voldoet het volgende dat ook doet.

Een voorbeeld
Een voorbeeld maakt het vast nog wat duidelijker.
Stel we kijken naar de som van de eerste n oneven getallen:
1 = 1
1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25

Het lijkt nu of, als we zo doorgaan, we alle kwadraten als som gaan krijgen. Maar is dat ook zo? Zou het niet bij bijvoorbeeld de miljoenste som 'mis' kunnen gaan?
Hiervoor kunnen we volledige inductie gaan gebruiken!!

Eerst maar eens onze veronderstelling netjes opschrijven:
$\sum$_k=1ⁿ2k-1 = n²

We beginnen met te kijken of het voor n=1 klopt.
$\sum$_k=1ⁿ2k-1 = n²
$\sum$_k=1¹2k-1 = 1 = 1²
Het klopt!!

Als we nu zouden kunnen bewijzen dat als het voor n geldt het ook voor n+1 geldt, zijn we klaar.
Want dan hebben we gecontrolleerd dat het voor n=1 klopt. Daarmee klopt het dus ook voor n=2, en dan dus ook voor n=3 enzovoort........

We gaan er dus vanuit dat geldt:
$\sum$_k=1ⁿ2k-1 = n²

Nu gaan we kijken naar de formule voor n+1:
$\sum$_k=1ⁿ⁺¹2k-1 =
{$\sum$_k=1ⁿ2k-1} + 2(n+1)-1 =
{$\sum$_k=1ⁿ2k-1} + 2n+1 =
n² + 2n+1 = (n+1)²
(bij de laatste regel hebben we de inductieveronderstelling ingevuld:
$\sum$_k=1ⁿ2k-1 = n²)

En dat is precies de veronderstelde eigenschap voor n+1.
En we hebben het nu bewezen.

Succes. Het is een kwestie van ermee oefenen om het goed te begrijpen wanneer je het wel of niet kunt gebruiken.
Kijk anders ook nog maar eens naar de andere voorbeelden die te vinden zijn op deze site.

gm
9-9-2003