Volledige Inductie

Het Principe der Volledige Inductie

Inhoud
Principe der Volledige Inductie Voorbeelden De som van een rekenkundige rij De som van een meetkundige rij Deelbaarheid Opgaven	Geschikt voor VWO 6

Principe der Volledige Inductie
Één van de pijlers van de moderne wiskunde is het "Principe der Volledige Inductie".

Zij P(n) een uitspraak, die gedefinieerd is voor elk natuurlijke getal n k (k ook een natuurlijk getal) met de volgende eigenschappen:

P(k) is waar
P(n+1) is waar, wanneer P(n) waar is

Dan is de uitspraak P(n) waar voor elk natuurlijke getal n k.

Het principe van de volledige inductie berust op het axioma van de volledige inductie geformuleerd door Peano (1858-1932). Met dit principe kunnen verschillende stellingen erg gemakkelijk bewezen worden.

Hoewel inductief redeneren in het dagelijks leven niet erg gebruikelijk is, vormt het toch de basis voor zeer belangrijk en fundamenteel onderzoek op tal van gebieden, met name de waarschijnlijkheidsrekening en de statistiek. De bedoeling van deze les is het "Principe van de Volledige Inductie" duidelijk te maken aan de hand van een aantal voorbeelden.

Voorbeeld
Stel we moeten de juistheid aantonen van een formule die afhankelijk is van het natuurlijk getal n, waarbij n = 0, 1, 2, 3, · · ·. In schoolboekjes wordt vaak het voorbeeld aangehaald van de formule voor de som der natuurlijke getallen 0 tot en met n.

S_n = 0 + 1 + 2 + 3 + · · · + n =

n(n + 1)

(n is een natuurlijk getal)

We willen in dit geval bewijzen dat de formule geldig is voor alle waarden van n 0. Je zou de formule kunnen verifiëren voor n = 0, n = 1, n = 2 tot en met n = 10.000. Zou de formule dan telkens kloppen dan zou je geneigd zijn aan te nemen dat de formule juist is voor alle waarden van n 0. Je weet dit echter niet zeker! Met het principe van de volledige inductie kunnen we de formule bewijzen voor alle n 0 .

De stappen bij een bewijs door volledige inductie zijn:

Ga na dat de formule juist is voor zekere n, n = k in bovenstaand voorbeeld
k = 0.
Neem aan dat de formule juist is voor n = m, waarbij m k.
Leidt hieruit af dat de formule juist is voor n = m + 1.
Hieruit mag je dan concluderen dat de formule juist is voor alle n k.

Immers als de formule juist is voor n = 0, dan is hij volgens stap III ook juist voor n = 1. Maar dan ook voor n = 2 enzovoort. Dit noemen we inductie. In de wiskunde wordt veel gebruik gemaakt van het principe van de volledige inductie om stellingen te bewijzen waarin het natuurlijk getal n voorkomt.

We gaan m.b.v. volledige inductie de juistheid van de formule

S_n = 0 + 1 + 2 + 3 + · · · + n =

n(n + 1)

(n = 0, 1, 2, 3, · · ·)

voor de som der natuurlijke getallen 0 tot en met n aantonen.

Stap I
We bewijzen eerst dat de formule juist is voor n = 0. Volgens de formule geldt:

S₀ =

0(0 + 1)

=0 en dit klopt!

De formule is dus juist voor n = 0.

Stap II
Stel de formule is juist voor n = m 0. Er geldt dus:

S_m = 0 + 1 + 2 + 3 + · · · + m =

m(m + 1)

Stap III
We gaan nu bewijzen dat hieruit volgt dat de formule is juist voor n = m+ 1, dus dat geldt:

S_m+1 = 0 + 1 + 2 + 3 + · · · + m + (m + 1) =

(m + 1)(m + 2)

Nu is

S_m+1

0 + 1 + 2 + 3 + · · · + m + (m + 1)

S_m + (m + 1)

m(m + 1)

+ (m + 1)

m(m + 1)

2(m + 1)

m(m + 1)+ 2(m + 1)

(m + 1)(m + 2)

Hetgeen te bewijzen viel!

Het bewijs kan ook vrij eenvoudig direct geleverd worden. Er geldt:

S_n

+ · · · +

n - 1

S_n

n - 1

n - 2

+ · · · +

2S_n

+ · · · +

(dit zijn n + 1 termen n)

n(n + 1)

Daaruit volgt:

S_n =

n(n + 1)

2

Hetgeen te bewijzen viel!

De som van een rekenkundige rij
Het bovenstaande voorbeeld is een bijzonder geval van een rekenkundige rij. Een rekenkundige rij is een rij van getallen a₀, a₁, a₂, · · · , a_n, a_n+1, · · · waarbij het verschil tussen twee opeenvolgende termen constant is. Voor een rekenkundige rij (a_n) geldt dus:

a_n+1 - a_n = constant = v (n 0)

We kunnen de algemene term a_n schrijven als:

a_n = a₀ + nv voor n = 0, 1, 2, 3, · · ·

Onder de som S_n verstaan we de som van n + 1 termen:

S_n = a₀ + a₁ + · · · + a_n =

i = 0

a_i

(n is een natuurlijk getal)

We gaan m.b.v. volledige inductie bewijzen dat:

S_n =

(n + 1)(a₀ + a_n)

Stap I
We gaan eerst bewijzen dat de formule juist is voor n = 0. Volgens de formule geldt:

S₀ =

(0 + 1)(a₀ + a₀)

2a₀

=a₀ en dit klopt!

De formule is dus juist voor n = 0.

Stap II
Stel de formule is juist voor n = m 0. Er geldt dus:

S_m = a₀ + a₁ + · · · + a_m =

(m + 1)(a₀ + a_m)

Stap III
We gaan nu bewijzen dat hieruit volgt dat de formule is juist voor n = m+ 1, dus dat geldt:

S_m+1 = a₀ + a₁ + · · · + a_m + a_m₊₁ =

((m + 1) + 1)(a₀ + a_m₊₁)

(m + 2)(a₀ + a_m₊₁)

Nu is

S_m+1

a₀ + a₁ + · · · + a_m + a_m₊₁

S_m + a_m₊₁

(m + 1)(a₀ + a_m)

+ a_m₊₁

(m + 1)(a₀ + a_m)

2a_m₊₁

(m + 1)(a₀ + a_m₊₁ - v)

a_m₊₁ + a_m₊₁

(m + 1)(a₀ + a_m₊₁) - (m + 1)v

a_m₊₁ + a_m₊₁

(m + 1)(a₀ + a_m₊₁) - (m + 1)v + a_m₊₁ + a_m₊₁

(m + 1)(a₀ + a_m₊₁) + a₀ + a_m₊₁

(m + 1)(a₀ + a_m₊₁) + 1(a₀ + a_m₊₁)

(m + 2)(a₀ + a_m₊₁)

Hetgeen te bewijzen viel!

Het bewijs kan ook vrij eenvoudig direct geleverd worden. Er geldt:

S_n

a₀

a₀ + v

a₀ + 2v

+ · · · +

a_n - v

a_n

S_n

a_n

a_n - v

a_n - 2v

+ · · · +

a₀ + v

a₀

2S_n

(a₀ + a_n)

+ · · · +

(a₀ + a_n)

n + 1 termen

(n + 1)(a₀ + a_n)

Daaruit volgt:

S_n =

(n + 1)(a₀ + a_n)

2

Hetgeen te bewijzen viel!

Een bewijs door volledige inductie bestaat dus steeds uit twee delen. Eerst het bewijs dat de uitspraak waar is voor n = 0. Dan dat uit de juistheid voor n = m de juistheid volgt voor n = m + 1. Deze twee stappen, samen met het principe van de volledige inductie, geven de juistheid voor alle n (n natuurlijk getal).

Soms is het handiger een bewijs m.b.v. volledige inductie te geven, b.v. als je al een vermoeden hebt van de formule maar nog moet bewijzen dat deze juist is. In de wiskunde wordt veel gebruik gemaakt van het principe van de volledige inductie om stellingen te bewijzen waarin het natuurlijk getal n voorkomt.

De som van een meetkundige rij
Een meetkundige rij is een rij van getallen a₀, a₁, a₂, · · · , a_n, a_n+1, · · · waarbij het quotiënt van twee opeenvolgende termen constant is. Voor een meetkundige rij (a_n) geldt dus:

a_n+1

a_n

= constant = r (r

1 en n 0)

De constante r wordt ook wel de reden genoemd. We kunnen de algemene term a_n schrijven als:

a_n = a₀rⁿ voor n = 0, 1, 2, 3, · · ·

Onder de som S_n verstaan we de som van n + 1 termen:

S_n = a₀ + a₁ + · · · + a_n =

i = 0

a_i

(n is een natuurlijk getal)

We gaan m.b.v. volledige inductie bewijzen dat:

S_n =

a₀ (1 - rⁿ^{+ 1})

1 - r

Stap I
We gaan eerst bewijzen dat de formule juist is voor n = 0. Volgens de formule geldt:

S₀ =

a₀ (1 - r^{0
+ 1})

1 - r

a₀ (1 - r)

1 - r

=a₀ en dit klopt!

De formule is dus juist voor n = 0.

Stap II
Stel de formule is juist voor n = m 0. Er geldt dus:

S_m = a₀ + a₁ + · · · + a_m =

a₀ (1 - r^m^{+ 1})

1 - r

Stap III
We gaan nu bewijzen dat hieruit volgt dat de formule is juist voor n = m + 1, dus dat geldt:

S_m+1 = a₀ + a₁ + · · · + a_m + a_m₊₁ =

a₀ (1 - r^m^{+ 2})

1 - r

Nu is

S_m+1

a₀ + a₁ + · · · + a_m + a_m₊₁

S_m + a_m₊₁

a₀ (1 - r^m^{+ 1})

1 - r

+ a₀r^m^{+ 1}

a₀ (1 - r^m^{+ 1})

1 - r

a₀(1 - r)r^m^{+ 1}

1 - r

a₀ (1 - r^m^{+ 1})

1 - r

a₀(r^m^{+ 1} - r^m^{+ 2})

1 - r

a₀ (1 - r^m^{+ 1}) + a₀(r^m^{+ 1} - r^m^{+ 2})

1 - r

a₀ (1 - r^m^{+ 1} + r^m^{+ 1} - r^m^{+ 2})

1 - r

a₀ (1 - r^m^{+ 2})

1 - r

Hetgeen te bewijzen viel!

Het bewijs kan ook vrij eenvoudig direct geleverd worden. Er geldt:

S_n

a₀

a₀r

a₀r²

+ · · · +

a₀rⁿ

rS_n

a₀r

a₀r²

+ · · · +

a₀rⁿ

a₀rⁿ⁺¹

(1 - r)S_n

a₀

+ · · · +

a₀rⁿ⁺¹

a₀ - a₀rⁿ⁺¹

a₀(1 - rⁿ⁺¹)

Daaruit volgt als r 1 (waarom?):

S_n =

a₀(1 - rⁿ⁺¹)

1 - r

Hetgeen te bewijzen viel!

Deelbaarheid
We gaan nu een wat ingewikkelder voorbeeld van een bewijs met volledige inductie bekijken. Als je dit voorbeeld begrijpt heb je het principe van het inductief redeneren aardig onder de knie. Voor de duidelijkheid formuleren we eerst nog een hulpstelling die we nodig hebben bij het bewijs van de Hoofdstelling.

Hulpstelling
Stel a, b en c zijn natuurlijke getallen waarvoor geldt: a 1, b 1, c 1 en a b. Stel verder dat a - b deelbaar is door c en dat b deelbaar is door c. Dan is ook a deelbaar door c.

Bewijs

Stel

a - b

= p (is een geheel getal) en

= q (is een geheel getal)

Dan is

a - b + b

a - b

= p - q (is een geheel getal)

Hetgeen te bewijzen viel!

De volgende Hoofdstelling is belangrijk i.v.m binomiaalcoëfficiënten. Het bewijs van deze stelling is een goede oefening in het toepassen van volledige inductie en logisch nadenken! Ga het bewijs stap voor stap na en let daarbij op het woordje elke.

Hoofdstelling
Zij n een natuurlijk getal met n 1. Een product van k 2 opeenvolgende getallen

n(n + 1)(n + 2) · · · (n + k - 1)

is deelbaar door

k! ( = 1 2 · · · k )

Bewijs
We gaan deze stelling bewijzen met volledige inductie naar k.

Stap I
We tonen eerst aan dat de stelling juist is voor elk natuurlijke getal n 1 en k = 2.

Voor elke n 1 is n(n + 1) deelbaar door 2! = 2, omdat één van de factoren
n en (n + 1) even moet zijn.

De stelling is dus juist voor k = 2 en elke n 1.

Stap II
Stel nu dat de stelling juist is voor elke n 1 en k 2 factoren. Dus dat voor elke n 1

n(n + 1)(n + 2) · · · (n + k - 1)

deelbaar is door

k! ( = 1 2 · · · k )

Stap III
We moeten nu aantonen dat uit de aanname in Stap II volgt dat voor elke n 1 en k +1 factoren geldt:

n(n + 1)(n + 2) · · · (n + k - 1)(n + k)

is deelbaar door

(k + 1)! ( = 1 2 · · · k (k + 1) = k! (k + 1))

Om dit te bewijzen gaan we verder met volledige inductie naar n. Hierbij mogen we nog steeds gebruik maken van de aanname in Stap II.

Stap 1
We tonen eerst aan dat de bewering uit Stap III juist is voor n = 1.
Voor n = 1 geldt:

n(n + 1)(n + 2) · · · (n + k - 1)(n + k) = 1 2 · · · k (k + 1)

en dit is zeker deelbaar door (k + 1)! = 1 2 · · · k (k + 1)
De bewering uit Stap III is dus juist voor n = 1.

Stap 2
We nemen nu aan dat de bewering uit Stap III juist is voor n = m. Dus er geldt:

m(m + 1)(m + 2) · · · (m + k - 1)(m + k)

is deelbaar door

(k + 1)! = 1 2 · · · k (k + 1)

Stap 3
We moeten nu laten zien dat de bewering uit Stap III juist is voor
n = m + 1. Dus dat

(m + 1)(m + 2)(m + 3) · · · (m + k)(m + k + 1 )

deelbaar is door

(k + 1)! = 1 2 · · · k (k + 1)

Nu komt het moeilijkste stukje van de logica van het bewijs. We gaan hierbij de hulpstelling gebruiken. Het verschil (vergelijk met het verschil
a - b in de hulpstelling)

(m+1)(m+2) · · · (m+k)(m+k+1) - m(m+1) · · · (m+k-1)(m+k) =

(m+k+1-m)(m+1)(m+2) · · · (m+k) =

(k+1)(m+1)(m+2) · · · (m+k) is deelbaar door (k + 1)!,

want het product van k factoren (m+1)(m+2) · · · (m+k) is volgens de aanname in Stap II namelijk deelbaar door k! en dus is (k+1)(m+1)(m+2) · · · (m+k) deelbaar door (k + 1)k! = (k + 1)!

Omdat we bij Stap 2 hebben aangenomen dat m(m+1) · · · (m+k-1)(m+k) deelbaar is door (k + 1)! volgt m.b.v. de hulpstelling dat ook

(m+1)(m+2) · · · (m+k)(m+k+1)

deelbaar is door (k + 1)!

Hiermee is bewezen dat bewering uit Stap III juist is voor elke n 1 en k +1 factoren. Hiermee is bovendien de Hoofdstelling bewezen m.b.v. volledige inductie. Bij dit bewijs is volledige inductie dus twee keer gebruikt.

Opgaven
Bewijs met volledige inductie dat de volgende stellingen voor elk natuurlijk getal n 1 juist zijn. Maak eerst zelf de opgaven alvorens je de uitwerkingen van de bewijzen gaat bekijken.

Stelling 1:

3 + 6 + 9 + · · · + 3(n - 1) + 3n =

n[6 + 3(n - 1)]

Bewijs

Stelling 2:

1 + 2 + 4 + 8 + · · · + 2^{n - 1} = 2ⁿ - 1

Bewijs

Stelling 3:

1² + 2² + 3² + · · · + n² =

n(n + 1)(2n + 1)

Bewijs

Stelling 4:

2n + 1

k = 2

k(k + 1)

2(n + 1)

Bewijs

Stelling 5:

k = 1

(-1)^{k
-1}

k = n + 1

Bewijs