Moet de basisstap altijd bij n = 1 liggen?

Nee. Begin bij de eerste waarde vanaf waar de uitspraak moet gelden. De som van machten van 2 begint bij $n = 0$. De uitspraak $2^n > n^2$ is onwaar voor $n = 2, 3, 4$ (bijvoorbeeld $2^4 = 16 = 4^2$) en geldt voor elke $n \ge 5$, dus dat bewijs gebruikt de basisstap $n = 5$.

Is volledige inductie hetzelfde als inductief redeneren in de natuurwetenschappen?

Nee. Bij inductief redeneren raad je een algemene regel uit voorbeelden, en die kan fout zijn. Volledige inductie is een deductief bewijs: zodra de basisstap en de inductiestap bewezen zijn, staat het resultaat vast.

Wat is sterke inductie?

Bij sterke inductie neemt de hypothese aan dat $P(1), P(2), \dots, P(k)$ allemaal waar zijn, niet alleen $P(k)$. Dat is handig als $P(k+1)$ van meerdere eerdere gevallen afhangt, bijvoorbeeld bij bewijzen over ontbinding in priemfactoren.

Leermiddelen

Volledige inductie

Q: Waarom bewijst inductie de uitspraak echt voor ALLE n?

De basisstap geeft $P(1)$. De stap met $k = 1$ geeft $P(2)$, met $k = 2$ geeft hij $P(3)$, enzovoort. Elk positief geheel getal wordt na eindig veel stappen bereikt, dus geen enkele $n$ wordt overgeslagen.

Leer uitspraken voor elk positief geheel getal te bewijzen met volledige inductie: basisstap, inductiehypothese, inductiestap en conclusie.

Gevorderd30 minLes

Werkblad om te printen

Definitie

Volledige inductie is een bewijsmethode voor uitspraken over elk positief geheel getal

n

(of elk geheel getal vanaf een startwaarde). We noemen de uitspraak

P(n)

. In plaats van oneindig veel gevallen één voor één te controleren, bewijs je maar twee dingen:

1.Basisstap: $P(1)$ is waar.
2.Inductiestap: voor elke $k \ge 1$ geldt: als $P(k)$ waar is, dan is $P(k+1)$ ook waar. De aanname " $P(k)$ is waar" heet de inductiehypothese.

Samen geven ze de conclusie:

P(n)

is waar voor elke

n \ge 1

P(1) \ \text{en} \ \big(P(k) \Rightarrow P(k+1)\big) \ \Longrightarrow \ P(n) \text{ voor alle } n \ge 1

Denk aan een oneindig lange rij dominostenen. De basisstap duwt de eerste steen om. De inductiestap garandeert dat elke vallende steen de volgende omduwt. Dus vallen alle stenen:

P(1)

, dan

P(2)

, dan

P(3)

, en zo verder zonder einde.

Probeer het meteen

Welke twee delen moet elk bewijs met volledige inductie bevatten?

Uitgewerkte voorbeelden

Bewijs dat $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ voor elke $n \ge 1$ .

Basisstap: controleer $n = 1$

Linkerkant: $1$ . Rechterkant: $\dfrac{1 \cdot 2}{2} = 1$ → $P(1)$ is waar

Inductiehypothese: neem $P(k)$ aan voor een $k \ge 1$

Stel dat $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ → Deze gelijkheid mogen we gebruiken

Inductiestap: tel de volgende term $k+1$ bij beide kanten op

$1 + \dots + k + (k+1) = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{k(k+1) + 2(k+1)}{2}$ → $= \dfrac{(k+1)(k+2)}{2}$

Vergelijk met $P(k+1)$

$P(k+1)$ zegt dat de som gelijk is aan $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ → $P(k+1)$ is waar

Antwoord: Met volledige inductie geldt $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ voor elke $n \ge 1$ . Bijvoorbeeld: $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$ .

Veelgemaakte fouten

De basisstap overslaan

Waarom het fout is: De inductiestap alleen bewijst niets: die zegt alleen dat ALS een steen valt, de volgende ook valt. Voorbeeld: de onjuiste bewering $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ heeft een inductiestap die werkt, maar voor $n = 1$ is de linkerkant $1$ en de rechterkant $2$ .

Correct: Controleer altijd expliciet het eerste geval. Zonder een eerste vallende steen valt er niets.

Aannemen wat je wilt bewijzen

Waarom het fout is: Wie "stel dat $P(n)$ waar is voor alle $n$ " of "stel dat $P(k+1)$ " schrijft, redeneert in een cirkel: de conclusie wordt al aangenomen.

Correct: Neem $P(k)$ aan voor ÉÉN waarde $k$ (de inductiehypothese) en bewijs daarmee $P(k+1)$ .

Verkeerde algebra in de inductiestap

Waarom het fout is: Een veelgemaakte fout is de verkeerde volgende term optellen, bijvoorbeeld $2k - 1$ in plaats van $2k + 1$ bij de som van oneven getallen, of vergeten de nieuwe term aan één kant op te tellen.

Correct: Schrijf eerst $P(k+1)$ volledig uit (vervang elke $n$ door $k+1$ ) en werk dan precies naar die uitdrukking toe.

Denken dat veel gecontroleerde gevallen een bewijs zijn

Waarom het fout is: De uitdrukking $n^2 + n + 41$ geeft priemgetallen voor $n = 0, 1, \dots, 39$ , maar voor $n = 40$ geeft ze $1681 = 41^2$ , en dat is geen priemgetal.

Correct: Voorbeelden helpen om een formule te vermoeden. Alleen de basisstap plus de inductiestap bewijzen haar voor elke $n$ .

Interactieve visualisatie

Rij-verkenner

Eerste term (a₁ = 1)

Verschil (d = 2)

11,

13,

, ...

Formule

a_n = 1 + 2(n - 1) = 2n - 1

Somformule: S_8 = 8/2 × (2×1 + 7×2) = 64

Partiële sommen

S₁ = 1S₂ = 4S₃ = 9S₄ = 16S₅ = 25S₆ = 36S₇ = 49S₈ = 64

a_1

a_5

a_10

a_20

Rij-verkenner

Eerste term (a₁ = 1)

Reden (r = 2)

16,

32,

64,

128

, ...

Formule

a_n = 1 × 2^(n-1)

Somformule: S_8 = 1 × (1 - 2^8) / (1 - 2) = 255

Partiële sommen

S₁ = 1S₂ = 3S₃ = 7S₄ = 15S₅ = 31S₆ = 63S₇ = 127S₈ = 255

|r| ≥ 1: de partiële sommen naderen geen vaste waarde, dus de oneindige reeks heeft geen som.

a_1

a_5

a_10

512

a_20

524.288

Interactieve sandbox

Expressiecalculator

Probeer deze:

Geschiedenis

Nog geen berekeningen

Oefenproblemen

18 opgaven

Opgave 1 van 18

Makkelijk

Welke twee delen moet elk bewijs met volledige inductie bevatten?

Waarom het belangrijk is

Inductie is het belangrijkste hulpmiddel om uitspraken over oneindig veel gevallen te bewijzen:

Somformules: je kunt bewijzen dat $1 + 2 + \dots + 100 = 5050$ volgt uit een algemene formule en geen toeval is
Informatica: programmeurs bewijzen dat lussen en recursieve functies voor elke invoergrootte het juiste resultaat geven
Patronen die waar lijken: een patroon dat in 40 gevallen klopt, kan bij geval 41 mislukken; inductie vertelt je wanneer een patroon echt altijd geldt
Puzzels en spellen: de Torens van Hanoi, betegelingsproblemen en veel olympiadeopgaven worden met inductie opgelost
Hogere wiskunde: bijna elk deel van de wiskunde gebruikt ergens inductie

In de vorige lessen heb je directe bewijzen geleerd. Inductie voegt een krachtig nieuw idee toe: bewijs één stap en laat die zich eindeloos herhalen.

Toepassingen in de echte wereld

Computerprogramma's controleren

Programmeurs gebruiken inductie om te bewijzen dat een lus na elk aantal rondes het juiste antwoord geeft: klopt het na $k$ rondes, dan klopt het ook na $k+1$ rondes.

Voorbeeld:

Een lus telt $1, 2, 3, \dots$ op bij een lopend totaal. Inductie bewijst dat het totaal na $n$ rondes gelijk is aan $\dfrac{n(n+1)}{2}$ .

1Probeer het zelf

Een programma telt in een lus de getallen van $1$ tot en met $100$ op.

Welk totaal geeft het programma?

Stap 1: Schrijf de wiskundige uitdrukking

Gebruik $\dfrac{n(n+1)}{2}$ met $n = 100$ :

De Torens van Hanoi

Bij deze puzzel verplaats je een stapel schijven naar een andere pin, steeds één schijf tegelijk, en nooit een grotere schijf op een kleinere. Inductie bewijst dat $n$ schijven $2^n - 1$ zetten nodig hebben.

Voorbeeld:

Om $k+1$ schijven te verplaatsen, zet je de bovenste $k$ schijven opzij, verplaats je de grootste schijf en zet je de $k$ schijven er weer bovenop: $2(2^k - 1) + 1 = 2^{k+1} - 1$ zetten.

2Probeer het zelf

Een toren heeft $6$ schijven. Het verplaatsen van $5$ schijven kost $31$ zetten.

Hoeveel zetten hebben $6$ schijven nodig?

Stap 1: Schrijf de wiskundige uitdrukking

Gebruik zetten voor 6 schijven $= 2 \cdot$ (zetten voor 5 schijven) $+ 1$ :

Rijstkorrels op het schaakbord

Een oude legende: leg $1$ rijstkorrel op het eerste veld, $2$ op het tweede, $4$ op het derde, en verdubbel steeds. De som van machten van 2 geeft je het totaal.

Voorbeeld:

Op de eerste $3$ velden liggen $1 + 2 + 4 = 7 = 2^3 - 1$ korrels.

3Probeer het zelf

Je vult de eerste $10$ velden. Op veld $10$ liggen $2^9$ korrels.

Hoeveel korrels liggen er samen op de eerste $10$ velden?

Stap 1: Schrijf de wiskundige uitdrukking

Gebruik $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ met $n = 9$ :

Belangrijke punten

1Volledige inductie bewijst een uitspraak $P(n)$ voor elk geheel getal $n$ vanaf een startwaarde
2Basisstap: laat zien dat het eerste geval, meestal $P(1)$ , waar is
3Inductiehypothese: neem aan dat $P(k)$ waar is voor een willekeurige $k$
4Inductiestap: gebruik de hypothese om $P(k+1)$ te bewijzen
5Conclusie: net als bij een rij dominostenen is de uitspraak waar voor elke $n$
6Beide delen zijn nodig: een inductiestap zonder basisstap, of een paar gecontroleerde gevallen zonder stap, bewijzen niets

Veelgestelde vragen

De basisstap geeft

P(1)

. De stap met

k = 1

geeft

P(2)

, met

k = 2

geeft hij

P(3)

, enzovoort. Elk positief geheel getal wordt na eindig veel stappen bereikt, dus geen enkele

n

wordt overgeslagen.

Woordenlijst

Volledige inductie: Een bewijsmethode die $P(n)$ bewijst voor elk geheel getal $n$ vanaf een startwaarde, met een basisstap en een inductiestap
Basisstap: Het eerste geval van de uitspraak, meestal $P(1)$ , dat direct wordt gecontroleerd
Inductiehypothese: De aanname dat $P(k)$ waar is voor een willekeurig geheel getal $k$
Inductiestap: Het bewijs dat uit $P(k)$ volgt dat $P(k+1)$ waar is, voor elke $k$ vanaf de startwaarde
P(n): De uitspraak die we willen bewijzen, geschreven als functie van het gehele getal $n$
Conclusie: De laatste zin van een inductiebewijs: $P(n)$ is waar voor elke $n$ vanaf de startwaarde

Formulekaart

Principe van volledige inductie

P(1) \text{ en } \big(P(k) \Rightarrow P(k+1)\big) \Rightarrow P(n) \text{ voor alle } n \ge 1

Basisstap plus inductiestap bewijzen de uitspraak voor elke $n$

Som van de eerste n gehele getallen

1 + 2 + \dots + n = \dfrac{n(n+1)}{2}

Voor $n = 5$: $15$

Som van de eerste n oneven getallen

1 + 3 + \dots + (2n-1) = n^2

Voor $n = 5$: $25$

Som van machten van 2

1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1

Voor $n = 6$: $127$

Meer over dit onderwerp

Definitie

Uitgewerkte voorbeelden

Veelgemaakte fouten

Interactieve visualisatie

Rij-verkenner

Formule

Partiële sommen

Rij-verkenner

Formule

Partiële sommen

Interactieve sandbox

Expressiecalculator

Geschiedenis

Oefenproblemen

Waarom het belangrijk is

Toepassingen in de echte wereld

Computerprogramma's controleren

De Torens van Hanoi

Rijstkorrels op het schaakbord

Belangrijke punten

Veelgestelde vragen

Woordenlijst

Formulekaart

Principe van volledige inductie

Som van de eerste n gehele getallen

Som van de eerste n oneven getallen

Som van machten van 2

Meer over dit onderwerp

Introductie tot wiskundige bewijzen

Direct bewijs

Bewijzen in twee kolommen

Bewijzen in alineavorm