Proof by induction

1. Introductie inductie

Deze manier van bewijzen gebruiken we wanneer er gevraagd wordt om een stelling te bewijzen voor alle natuurlijke getallen. Een stelling als bijvoorbeeld: Bewijs dat (9ⁿ)-1 deelbaar is voor elk natuurlijk getal n≥1.

Legenda

∠ = Hoek
≈ = Ongeveer gelijk aan
° = Graden
< = Kleiner dan
> = Groter dan

2. Volledige inductie

Omdat we moeilijk een stelling kunnen bewijzen voor letterlijk elk natuurlijk getal, maken we gebruik van volledige inductie. Met volledige inductie testen we of een stelling voor een beginwaarde n waar is en vervolgens bewijzen we dat de formule voor alle opvolgende waardes van n waar is. Dit doen we door n te substitueren met n+1. Dit wordt ook wel het domino-effect genoemd. Want elk getal dat je invult voor n in n+1, bewijst het volgende getal, omdat er +1 achter staat. Elke steen die omvalt laat z’n opvolger omvallen. Valt de eerste steen om, dan zullen alle stenen omvallen.

Om iets te bewijzen maken we gebruik van 4 stappen. In het Engels heeft dit een mooi ezelsbruggetje: TAPE. Dit staat voor: Test, Assume, Prove en Explain.

Stap 1: Test
We testen als eerste of de stelling überhaupt waar is door een startwaarde n in te vullen in de stelling. Klopt de stelling voor deze waarde, dan gaan we door naar stap 2.
Stap 2: Assume
We nemen aan dat, uit stap 1, de stelling waar is voor n.
Stap 3: Prove
We bewijzen dat de stelling waar is voor alle opvolgende getallen door n te substitueren met n+1.
Stap 4: Explain
We geven een conclusie die we trekken uit het bewijs.

3. Voorbeeld #1 volledige inductie

Bewijs dat (9ⁿ)-1 deelbaar is door 8 voor elk natuurlijk getal n≥1.

Stap 1: We beginnen dus met het testen of de bewering klopt voor de startwaarde van en n=1:
In dit geval ligt de startwaarde vanaf waar we het domino-effect gaan toepassen op 1, omdat n≥1.

(9n)-1

(91)-1 Substitutie voor n=1

8 Uitwerken

Dit is deelbaar door 8. Dus de bewering is waar voor n=1.

Stap 2: Neem aan dat de bewering waar is voor n=m met m∈N dus:
(9m)-1

Stap 3: Bewijs dat als de stelling waar is voor een getal (m) dat het waar is voor de volgende getallen (m+1).
Om te bewijzen dat P(m+1) deelbaar is door 8, willen we de originele vorm van de stelling, (9ⁿ)-1, weer terugkrijgen in ons antwoord, omdat we al weten dat dit deelbaar is door 8.

(9m)-1

(9m+1)-1 Substitutie voor m=m+1

9m · 91 -1 Exponenten opsplitsen

9m · 9 -1 Exponenten wegwerken

9(9m-1) +8 Factor 9 buiten haakjes halen en compenseren met +8

Stap 4: Redeneren
Van 9(9m-1)+8 weten we sowieso dat (9m-1) een 8-voud is aangezien we dit in stap 1 hebben laten zien.
9(9m-1) Dit is dan 9 maal een 8-voud. Wat nog steeds een 8-voud is.
9(9m-1)+8 Dit is 9 maal een 8voud + 8. Wat ook nog steeds een 8-voud is.
Dus (9n)-1 is deelbaar door 8 voor elk natuurlijk getal n≥1.

Q.E.D.

4. Voorbeeld #2 volledige inductie

Bewijs door middel van volledige inductie dat 5ⁿ−2ⁿ deelbaar is door 3 voor alle n∈N.

Stap 1: Testen of de bewering klopt voor de startwaarde van en n=0:

5ⁿ-2ⁿ

5⁰ – 2⁰ Substitutie voor n=0

1 – 1 Machten uitwerken

Uit de bovenstaande substitutie volgt 0, en 0 is deelbaar door 3, dus is een 3-voud.
Laten we het voor de zekerheid ook testen voor n=1.

5¹ – 2¹ Substitutie voor n=1

5-2 Machten uitwerken

3 termen aftrekken

Uit de bovenstaande uitwerking volgt 3, en 3 is ook deelbaar door 3, dus is een 3-voud.

Stap 2: Neem aan dat de bewering waar is voor n=m met m∈N dus:
5^m-2^m

Stap 3: Bewijs dat als de stelling waar is voor een getal (m) dat het waar is voor de volgende getallen (m+1).

5m-2m

5m+1-2m+1 Substitutie voor m=m+1

5·5m– 2·2m Kwadraten opsplitsen

3·5m + 2·5m – 2·2m 5·5 opsplitsen in factor 3, omdat we moeten bewijzen dat het deelbaar is door 3

3·5m + 2(5m -2m)

Gelijke factor 2 buiten haakjes halen om (5^m -2^m) uit stap 1 weer terug te krijgen

Stap 4: Redeneren
3·5^m is een 3-voud.
Uit stap 1 weten we dat 5^m −2^m een 3-voud is.
Dus is 2(5m -2m), 2 maal een 3-voud.
En dat betekent dat 5n−2n een drievoud is voor alle n∈N.

Q.E.D.

5. Voorbeeld #3 volledige inductie

Bewijs dat (5ⁿ)-1 is deelbaar door 4 voor alle n∈N.

Stap 1: Testen of de bewering klopt voor de startwaarde van en n=0:

(5n)-1

(50)-1 Substitutie voor n=0

(1)-1 Machten uitwerken

0 termen uitwerken

Uit de bovenstaande uitwerking volgt 0, en 0 is deelbaar door 4, dus is een 4-voud.
Laten we het voor de zekerheid ook testen voor n=1.

(51)-1 Substitutie voor n=1

(5)-1 Machten uitwerken

4 Termen uitwerken

Uit de bovenstaande uitwerking volgt 4, en 4 is ook deelbaar door 4, dus is een 4-voud.

Stap 2: Neem aan dat de bewering waar is voor n=m met m∈N dus:
(5m)-1

Stap 3: Bewijs dat als de stelling waar is voor een getal (m) dat het waar is voor de volgende getallen (m+1).

(5m)-1

(5m+1)-1 Substitutie voor m=m+1

5(5m)-1 Kwadraten opsplitsen

5(5m-1)+4 -1 binnen haakjes werken zodat we (5m-1) uit stap 1 weer terugkrijgen. Vervolgens compenseren met +4

Stap 4: Redeneren
We weten hiervan dat (5m-1) al een 4-voud is uit stap 1.
5(5m-1) is dus 5 maal een 4-voud, wat nog steeds een 4-voud is.
5(5m-1)+4 is 5 maal een 4-voud + 4 wat ook nog steeds een 4-voud is.
Dus (5n-1) is een 4-voud voor alle n∈N.

Q.E.D

6. Volledig inductie voor formules en ongelijkheden

Volledige inductie wordt ook vaak gebruikt om formules en ongelijkheden te bewijzen. Hierbij zie je deze vaak staan de volgende notatie.
Bewijs dat:
3+7+11+…+(4n+3) = 2n²+5n+3 voor alle n ∈N.

Het is sowieso handig eerst te weten hoe je dit moet aflezen. De som aan de linkerkant van het = teken is de som van alle waarden van n met als formule (4n+3). In de tabel hieronder zie je de waarden die we krijgen als we n invullen in (4n+3).

Dus de som die je ziet aan de linker kant van het = teken, is de som voor alle n waardes die je invult in (4n+3). Dit ziet er als volgt uit:

(4n + 3)

(4·0+3) = 3 Substitutie voor n=0

(4·0+3)+(4·1+3) = 10 Substitutie voor n=1

(4·0+3)+(4·1+3)+(4·2+3) = 21 Substitutie voor n=2

Dus je ziet dat als je n=2 invult, dat we ook alle voorgaande waardes van n invullen voor de sommatie. De som van deze getallen aan de linkerkant van het = teken, staat gelijk aan de formule aan de rechterkant van het = teken. Vullen we in de vergelijking bijvoorbeeld in n=2. Dan krijgen we:

3 + 7 + 11 + … + (4n+3) = 2n²+ 5n + 3 De originele formule

(4·0+3) + (4·1+3) + (4·2+3) = 2(2²)+ 5(2) + 3 Substitutie voor n=2

(3) + (7) + (11) = (8) + (10) + 3 Haakjes uitwerken

21 = 21 Termen optellen

Laten we nu eens proberen deze vergelijking op te lossen doormiddel van volledige inductie.

Stap 1: Testen of de bewering klopt voor de startwaarde van en n=0:

3 + 7 + 11 + … + (4n + 3) = 2n²+ 5n + 3 De originele formule

(4·0 + 3) = 2(0²)+ 5(0) + 3 Substitutie voor n=0

3 = 0+ 0 + 3 Haakjes uitwerken

Hieruit blijkt dat de bewering waar is voor een startwaarde van n=0.

Stap 2: Neem aan dat de bewering waar is voor n=m met m∈N dus:
3 + 7 + 11 + … + (4m + 3) = 2m2+ 5m + 3

Stap 3: Bewijs dat als de stelling waar is voor een getal (m) dat het waar is voor de volgende getallen (m+1).

3 + 7 + 11 + … + (4(m+1) + 3) = 2(m+1)²+ 5(m+1) + 3 Substitutie voor m=m+1

Omdat we weten dat de vergelijking klopt voor een waarde (m) uit stap 1, willen we deze vorm van de vergelijking weer terugkrijgen in onze uitwerking. De originele vergelijking was als volgt:
3 + 7 + 11 + … + (4n + 3) = 2n2+ 5n + 3
In principe is deze vergelijking gelijk aan de vergelijking met (m+1), alleen heeft de vergelijking van (m+1) een extra term t.o.v. de vergelijking (m). Namelijk de +1.
Deze vergelijking uit stap 1, kunnen we gelijkstellen tot de vergelijking van (m+1) door aan beide kanten de extra term op te tellen.

3 + 7 + 11 + … + (4m + 3) = 2m²+ 5m + 3 De originele formule

3 + 7 + 11 + … + (4m + 3) + (4(m+1) + 3) = 2m²+ 5m + 3 + (4(m+1) + 3) Aan beide kanten de extra term (4(m+1) + 3) optellen

3 + 7 + 11 + … + (4m + 3) + (4(m+1) + 3) = 2m²+ 5m + 3 + 4m+4 + 3) Rechts haakjes uitwerken

3 + 7 + 11 + … + (4m + 3) + (4(m+1) + 3) = 2m²+ 9m + 10 Rechts gelijke termen optellen

3 + 7 + 11 + … + (4m + 3) + (4(m+1) + 3) = 2(m+1)²+ 5m + 10 -2 Rechts 2 buiten haakjes halen en compenseren met -2

3 + 7 + 11 + … + (4m + 3) + (4(m+1) + 3) = 2(m+1)²+ 5(m+1)+10-2-5 Rechts 5 buiten haakjes halen en compenseren met -5

3 + 7 + 11 + … + (4m + 3) + (4(m+1) + 3) = 2(m+1)²+ 5(m+1)+3 Rechts termen uitwerken

Nu hebben we rechts van het = teken weer uitgewerkt tot de vergelijking van (m+1). Wat we nu alleen nog hoeven te doen, is de links van het = teken, gelijk stellen met rechts. Hiervoor beginnen we eerst met substitutie. Links van het = teken staat “3 + 7 + 11 + … + (4m + 3)”. Uit stap 1 hebben we gezien dat dit gelijk staat aan “2m2+ 5m + 3“. Dus dit kunnen we invullen in de vergelijking en vervolgens verder uitwerken.

2m2+ 5m + 3 + (4(m+1) + 3) = 2(m+1)²+ 5(m+1)+3 Substitutie van (m)=2m²+ 5m + 3

2m2+ 5m + 3 + (4m+4) + 3) = 2(m+1)²+ 5(m+1)+3 Factor 4 uitwerken

2m2+ 9m + 10 = 2(m+1)²+ 5(m+1)+3 Gelijke termen optellen

2(m+1)2+ 5m + 10 -2 = 2(m+1)²+ 5(m+1)+3 2 buiten haakjes halen en compenseren met -2

2(m+1)2+ 5(m+1) + 10 -2 -5 = 2(m+1)²+ 5(m+1)+3 5 buiten haakjes halen en compenseren met -5

2(m+1)2+ 5(m+1) + 3 = 2(m+1)²+ 5(m+1)+3 Termen uitwerken

Stap 4: Redeneren
Wat we nu hebben gedaan is in stap 1 bewijzen dat de vergelijking klopt voor een startwaarde n.
In stap 3 hebben we bewezen dat de vergelijking klopt voor een waarde van n+1.
Dus 3 + 7 + 11 + … + (4n + 3) is gelijk aan 2n² + 5n + 3 voor alle n ∈N.

Q.E.D.

7. Voorbeeld volledig inductie voor formules en ongelijkheden

Bewijs door middel van volledige inductie dat: 1+2+3+ … + n = ¹₂ n(n+1)

Stap 1: Testen of de bewering klopt voor de startwaarde van en n=0:

1+2+3+ … + n = ¹₂ n(n+1) De originele formule

0 = ¹₂ 0(0+1) Substitutie van n=0

0 = 0 Uitwerken

Hieruit blijkt dat de bewering waar is voor een startwaarde van n=0

Stap 2: Neem aan dat de bewering waar is voor n=m met m∈N dus:

1+2+3+ … + m = ¹₂ m(m+1) Substitutie van n=m

Stap 3: Bewijs dat als de stelling waar is voor een getal (m) dat het waar is voor de volgende getallen (m+1).

1+2+3+ … + (m+1) = ¹₂ (m+1)((m+1)+1) Substitutie van m=m+1

1+2+3+ … + (m+1) = ¹₂ (m+1)(m+2) Termen optellen

Wat we nu hierboven hebben staan, is waar we naar toe willen werken met onze originele vergelijking van:

1+2+3+ … + m = ¹₂ m(m+1)

Deze vergelijking uit stap 1, kunnen we gelijkstellen tot de vergelijking van (m+1) door aan beide kanten de extra term op te tellen.

1+2+3+ … + m = ¹₂ m(m+1) Originele vergelijking

1+2+3+ … + m + (m+1) = ¹₂ m(m+1) + (m+1) Extra term van (m+1) aan beide kanten toevoegen

1+2+3+ … + m + (m+1) = ¹₂ m² ¹₂ m + (m+1) Haakjes uitwerken

Nu kunnen we rechts gaan terugwerken naar de originele vorm van (m+1).

1+2+3+ … + m + (m+1) = ¹₂ (m² +m +2m+2) De breuk buiten haakjes werken

1+2+3+ … + m + (m+1) = ¹₂ (m² +3m+2) Gelijke termen optellen

1+2+3+ … + m + (m+1) = ¹₂ (m+1)(m+2) Kwadraat afsplitsen

Nu moeten we als laatste de linker kant nog gelijkstellen aan de rechter kant. Dit kunnen we weer doen door “1+2+3+ … + m” te substitueren met: ¹₂ m(m+1)

Dit kunnen we doen omdat we hebben gezien in stap 1 dat deze 2 aan elkaar gelijk staan. Dan krijgen we de volgende uitwerking.

¹₂ m(m+1) + (m+1) = ¹₂ (m+1)(m+2) Substitutie van (m)= ¹₂ m(m+1)

¹₂ m² ¹₂ m + (m+1) = ¹₂ (m+1)(m+2) Haakjes uitwerken

¹₂ (m² +m +2m+2) = ¹₂ (m+1)(m+2) De breuk buiten haakjes wereken

¹₂ (m² +3m+2) = ¹₂ (m+1)(m+2) Gelijke termen optellen

¹₂ (m+1)(m+2) = ¹₂ (m+1)(m+2) Kwadraat afsplitsen

Stap 4: Redeneren
Wat we nu hebben gedaan is in stap 1 bewijzen dat de vergelijking klopt voor een startwaarde n.
In stap 3 hebben we bewezen dat de vergelijking klopt voor de volgende waardes van n+1.
Dus is deze vergelijking waar voor alle n ∈N.

Q.E.D.

SOCIAL MEDIA

SEARCH

$Math logo factorials$

Math

Factorials

November 12, 2019

$Math logo proof-80$

Math