Bewijs door Volledige Inductie




Basis-idee

Het komt veel voor dat men de geldigheid van een bewering moet aantonen voor alle natuurlijke getallen vanaf een zeker rangnummer. Dat rangnummer is veelal 0 of 1. Neem verder even aan dat het start-rangnummer 1 is.

Voorbeeld: 'De som van de natuurlijke getallen van 1 tot n is gelijk aan n(n+1)/2'.

Dit is een eigenschap welke van n afhangt. We noteren die eigenschap E(n). E(3) betekent in ons voorbeeld:
' De som van de natuurlijke getallen van 1 tot 3 is gelijk aan 3(3+1)/2 '

De bewijsmethode door volledige inductie is een veel gebruikte methode om een dergelijke eigenschap te bewijzen.
We tonen hoe de methode werkt en waarom ze correct is.

Noem V = { n | E(n) is waar }. Men bewijst eerst E(1). Als dat klaar is, weten we dat 1 zeker tot V behoort.

Dan toont men dan aan dat:
Als de eigenschap E(k) waar is, dan is E(k+1) waar.

Als dat ook bewezen is, weten we dat als k in V zit, (k+1) ook in V zit.

Maar 1 zit in V, dus zit 2 in V, dus zit 3 in V , en zo verder.

Dus V is ={ 1,2,3,4,....}

We hebben op die manier aangetoond dat de eigenschap E(n) waar is voor alle natuurlijke getallen vanaf 1.

Toepassing op ons voorbeeld

In dit voorbeeld is de eigenschap E(n) = 1+2+3+4+5+...+ n = (1+n)n/2 Besluit: de eigenschap is bewezen voor alle natuurlijke getallen vanaf 1.

Praktische werkwijze

Eenmaal dit principe duidelijk is wordt de procedure van het bewijs gewoonlijk sterk ingekort.

We hernemen het zelfde voorbeeld, maar geven de beknopte versie.

Te bewijzen: 1+2+3+4+5+...+ n = (1+n)n/2

Bewijs:

Voor n = 1 is de eigenschap waar want 1 = (1+1).1/2

Onderstel dat de eigenschap geldt voor n = k
Dus we weten dan dat 1+2+3+4+5+...+k = (1+k)k/2

We moeten bewijzen dat ze geldt voor n = k+1
Te bewijzen: 1+2+3+4+5+...+k+(k+1) = (1+(k+1)).(k+1)/2

linker lid = (1+2+3+4+5+...+k)+ (k+1) = (1+k).k/2 + (k+1) = (k+1)(k+2)/2 = rechter lid.

Dus is de eigenschap geldig voor alle n.

Voorbeeld 2

Afspraak: '>=' betekent 'groter of gelijk aan'

Toon aan dat voor alle gehele getallen groter dan 0 geldt: 2n >= n+1.

De eigenschap is vanzelfsprekend voor n=1.

Onderstel dat de eigenschap geldt voor n = k
Dus we weten dat 2k >= k+1.
Het is van groot belang dat we dit gebruiken in het bewijs.

We moeten bewijzen dat ze geldt voor n = k+1
Te bewijzen: 2k+1 >= k+2

Welnu 2k+1 = 2k.2 >= (k+1).2 = 2k+2 >= k+2

Dus is de eigenschap is geldig voor alle n.

Voorbeeld 3

Toon aan dat Sn = 1 + 3 + 5 + 7 + ... + 2n-1 = n2

De eigenschap is vanzelfsprekend voor n=1.

Onderstel dat de eigenschap geldt voor n = k
Dus we weten dat Sk = 1 + 3 + 5 + 7 + ... + 2k-1 = k2
Het is van groot belang dat we dit gebruiken in het bewijs.

We moeten bewijzen dat ze geldt voor n = k+1
Te bewijzen: Sk+1 = 1 + 3 + 5 + 7 + ... + 2k-1 + 2k+1 = (k+1)2
Welnu: Sk+1 = Sk + (2k+1) = k2 + 2k +1 = (k+1)2.

Dus is de eigenschap is geldig voor alle n.

Voorbeeld 4

Toon aan dat 12 + 22 + 32 + ... + n2 = (1/6). n.(n+1).(2n+1)

De eigenschap is vanzelfsprekend voor n=1.

Onderstel dat de eigenschap geldt voor n = k
Dus we weten dat 12 + 22 + 32 + ... + k2 = (1/6). k.(k+1).(2k+1)
Het is van groot belang dat we dit gebruiken in het bewijs.

We moeten bewijzen dat ze geldt voor n = k+1
Te bewijzen: 12 + 22 + 32 + ... + k2 + (k+1)2 = (1/6).(k+1).(k+2)(2k+3)
We omvormen linkerlid en rechterlid van het te bewijzen naar elkaar toe, en we zullen zien dat ze gelijk zijn.

 
Linkerlid

 = 12 + 22 + 32 + ... + k2 + (k+1)2

 = (12 + 22 + 32 + ... + k2) + (k+1)(k+1)

 = (1/6). k.(k+1).(2k+1) + (k+1)(k+1)

 = (1/6).(k+1). [ k(2k+1) + 6(k+1)]

 = (1/6).(k+1).(2 k2 + 7k + 6)

Rechterlid

 = (1/6).(k+1).(k+2)(2k+3)

 = (1/6).(k+1).(2k2 + 3k + 4k + 6)

Voorbeeld 5

Toon aan dat 32n+1 + 2n-1 een 7-voud is

De eigenschap is vanzelfsprekend voor n=1.

Onderstel dat de eigenschap geldt voor n = k.
Dus 32k+1 + 2k-1 is een 7-voud
Het is van groot belang dat we dit gebruiken in het bewijs.

We moeten bewijzen dat ze geldt voor n = k+1
Te bewijzen: 32k+3 + 2k is een 7-voud

We omvormen 32k+3 + 2k zodanig dat 32k+1 + 2k-1 erin voorkomt.

 
   32k+3 + 2k

 = 32.32k+1 + 2.2k-1

 = 9. 32k+1 + 2. 2k-1

 = 7. 32k+1 + 2. 32k+1 + 2. 2k-1

 = 7-voud + 2 (32k+1 + 2k-1)

 = 7-voud + 2 . 7-voud

 = 7-voud

Voorbeeld 6

Toon aan dat voor elk even getal n geldt

12 - 22 + 32 - 42 + ... - n2 = (-1/2) n (n+1)


De eigenschap is vanzelfsprekend voor n = 2.

Onderstel dat de eigenschap geldt voor n = k met k even.
Dus 12 - 22 + 32 - 42 + ... - k2 = (-1/2) k (k+1)

We moeten nu bewijzen dat ze geldig is voor n = k + 2
Te bewijzen:
12 - 22 + 32 - 42 + ... - k2 + (k+1)2 - (k+2)2 = (-1/2)(k+2)(k+3)

Bewijs:

 
   12 - 22 + 32 - 42 +  ... - k2 + (k+1)2 - (k+2)2

= (12 - 22 + 32 - 42 +  ... - k2) + (k+1)2 - (k+2)2

=             (-1/2) k (k+1)           + ((k+1)2 - (k+2)2 )

    we ontbinden het rechtse deel in factoren

= (-1/2) k (k+1) + ((k+1) -(k+2)).((k+1) + (k+2))

= (-1/2) k (k+1) + (-1) (2k + 3)

= (-1/2) ( k(k+1) + 4k + 6)

= (-1/2) ( k2 + 5k + 6 )

= (-1/2) (k + 2)(k + 3)
Opmerking:
Deze eigenschap kan ook bewezen worden zonder gebruik te maken van volledige inductie.
Een uitgewerkte methode zie je via deze link.

Redeneringsfout?

We tonen aan dat in elke doos met n balletjes, alle balletjes even groot zijn.

De eigenschap is vanzelfsprekend voor n = 1.

Onderstel dat de eigenschap geldt voor n = k.
Nu geldt : In elke doos met k balletjes, zijn alle balletjes even groot. (*)

Neem nu een doos met k+1 balletjes. We schrijven op een willekeurig balletje de letter A en op een ander willekeurig balletje de letter B. Om aan te tonen dat alle balletjes even groot zijn is het voldoende aan te tonen dat die willekeurig gekozen balletjes A en B even groot zijn.

We halen nu een balletje, verschillend van A en B, uit de doos. De doos bevat nu k balletjes. Steunend op (*) weten we dat die k balletjes even groot zijn. Dus balletje A is even groot als balletje B.

Besluit: in elke doos met n balletjes, zijn alle balletjes even groot.

--------

Verklaar nu nauwkeurig waarom deze redenering verkeerd is.




MATH-abundance - tutorial

Site adres is http://home.scarlet.be/math/nl/

Zend alle vragen, foutmeldingen en opmerkingen naar Johan.Claeys@ping.be
Het onderwerp of subject van de mail moet het woord 'wiskunde' bevatten omdat andere mails weggefilterd worden.