Docentenhandleiding: Volledige inductie

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

Les presenterenStudentpagina bekijken

Gebruik deze les in de klas

Gratis, leerlingen hebben geen account nodig.

Delen met leerlingen

Leerlingen openen de les en oefenen met directe feedback.

Werkblad om te printen

Alle oefenopgaven op papier, met een apart antwoordblad.

Werkblad Antwoorden

Klassenquiz

10 vragen over Wiskundige bewijzen. Leerlingen doen mee met een naam, jij ziet alle scores.

Voor docenten

Leerdoelen

Het dominoprincipe achter volledige inductie uitleggen
De basisstap, inductiehypothese, inductiestap en conclusie van een inductiebewijs opschrijven
Somformules, deelbaarheidsuitspraken en ongelijkheden met inductie bewijzen
Fouten in onjuiste inductiebewijzen vinden en verbeteren

Vereisten

• Introductie tot wiskundige bewijzen: wat een bewijs is
• Direct bewijs: uitspraken bewijzen vanuit definities
• Haakjes uitwerken en ontbinden van uitdrukkingen zoals $(k+1)^2$ en $(k+1)^3$
• Rekenen met machten, bijvoorbeeld $2 \cdot 2^k = 2^{k+1}$

Discussiestarters

1. Als je weet dat de eerste dominosteen valt en elke steen de volgende omduwt, hoe weet je dan dat de 1000e steen valt?
2. Waarom is het niet genoeg om een formule voor de eerste 40 waarden van n te controleren?
3. Wat zou er misgaan als we de basisstap overslaan?
4. Ken je een situatie uit het dagelijks leven waarin een stap altijd tot de volgende leidt?

Veelvoorkomende misvattingen

$P(k)$ aannemen betekent aannemen wat we willen bewijzen

Herstel: Benadruk dat we $P(k)$ maar voor ÉÉN waarde aannemen, om de verbinding van $k$ naar $k+1$ te laten zien. De basisstap zet de keten in gang. Gebruik de dominostenen: we nemen alleen aan dat een steen valt om te controleren of hij de volgende raakt.

De basisstap is een formaliteit die je kunt overslaan

Herstel: Laat de onjuiste bewering $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ zien. De inductiestap werkt perfect, maar de basisstap faalt, dus de bewering is onwaar voor elke $n$ .

Een paar gecontroleerde waarden bewijzen een formule

Herstel: Gebruik $n^2 + n + 41$ , dat priem is voor $n = 0$ tot en met $39$ maar gelijk is aan $41^2$ voor $n = 40$ . Patronen suggereren een formule, alleen een bewijs bevestigt haar.

DifferentiatieIdeeën

Voor leerlingen met moeite:

• Geef een sjabloon met vier vakken: basisstap, hypothese, stap, conclusie
• Controleer voor de algebra $P(k)$ en $P(k+1)$ met getallen, bijvoorbeeld $k = 4$
• Begin alleen met somformules, waarbij de volgende term makkelijk te zien is

Voor leerlingen op niveau:

• De som van oneven getallen en de som van machten van 2 bewijzen zonder sjabloon
• De fout vinden in drie onjuiste inductiebewijzen
• Bewijzen dat $n^3 - n$ deelbaar is door $3$

Voor gevorderde leerlingen:

• $2^n > n^2$ bewijzen voor $n \ge 5$ en uitleggen waarom de basisstap bij $5$ ligt
• $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$ bewijzen
• Sterke inductie leren en bewijzen dat elk geheel getal $n \ge 2$ een product van priemgetallen is

Standaarduitlijning

MP3 (CCSS.MATH.PRACTICE.MP3)
Steekhoudende argumenten opbouwen en de redenering van anderen kritisch beoordelen
HSA-APR.C.4 (CCSS.MATH.CONTENT.HSA.APR.C.4)
Polynoomidentiteiten bewijzen en gebruiken om getalsmatige verbanden te beschrijven
HSA-SSE.B.4 (CCSS.MATH.CONTENT.HSA.SSE.B.4)
De formule voor de som van een eindige meetkundige reeks afleiden en gebruiken om problemen op te lossen

Lesbronnen

visualRijen-visualisatie
Zet de eerste term op 1 en het verschil op 2: de somregel laat zien dat de eerste 8 oneven getallen samen 64 zijn, dus 8 in het kwadraat
activityDominodemonstratie
Leerlingen zetten een rij dominostenen neer en testen wat er gebeurt zonder eerste duw of met een gat in de rij
worksheetVul het inductiebewijs aan
Vijf inductiebewijzen waarin basisstappen, hypotheses en rekenstappen ontbreken

Lesinhoud

Alles wat leerlingen zien: definitie, voorbeelden, veelgemaakte fouten, toepassingen. Tik om te openen.

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.

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$ .

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

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.

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.

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

Docentenhandleiding: Volledige inductie

Gebruik deze les in de klas

Voor docenten

Voor leerlingen met moeite:

Voor leerlingen op niveau:

Voor gevorderde leerlingen:

Lesinhoud

Definitie

Uitgewerkte voorbeelden

Veelgemaakte fouten

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