Volledige inductie

Prioriteit: 🟠 Midden

SE-1 · weging 33⅓% · hoofdstuk 7. Een vast type opgave met een vaste opbouw: deelbaarheid, somformules met $\sum$ en ongelijkheden (diagnostische toets 8, gemengde opgave 28–29).

Wat moet je kunnen?

• Het driestappenschema volledig en netjes opschrijven.
• Deelbaarheid bewijzen door de uitdrukking voor $p+1$ te splitsen in een veelvoud plus de inductiehypothese.
• Somformules bewijzen via $\sum _{k=1}^{p+1}=\sum _{k=1}^p+(\text{term }p+1)$.
• Ongelijkheden bewijzen voor $n\ge n_0$.

De kern

Bewijs met volledige inductie

1. Inductiebasis: bewijs dat de bewering waar is voor $n=0$ (of de kleinste gevraagde $n$).
2. Inductiehypothese: neem aan dat de bewering waar is voor $n=p$. Inductiestap: bewijs dat ze dan ook waar is voor $n=p+1$.
3. Conclusie: de bewering is waar voor alle natuurlijke getallen (vanaf de basis).

Type	Truc in stap 2
deelbaarheid	schrijf de uitdrukking voor $p+1$ als $(\text{veelvoud van }d)+c\cdot (\text{hypothese})$
somformule	splits de laatste term af en vul de hypothese in
ongelijkheid	gebruik de hypothese en laat zien dat het restant groot genoeg is

Zo wordt het gevraagd

• “Bewijs met volledige inductie: 3²ⁿ⁺¹ + 2ⁿ⁻¹ is deelbaar door 7 voor elk natuurlijk getal n ≥ 1.” (diagnostische toets 8a).
• “Bewijs dat ${\sum }_{k=1}^n(4k-1)=2n^2+n$ voor elk natuurlijk getal n ≥ 1.” (diagnostische toets 8b).
• “Bewijs dat n! > 2ⁿ voor elk natuurlijk getal n ≥ 4.” (opgave 36).

Uitgewerkt voorbeeld

Deelbaarheid (vergelijk H7 diagnostische toets 8a)

Bewijs dat $3^{2n+1}+2^{n-1}$ deelbaar is door 7 voor elk natuurlijk getal $n\ge 1$.

1. $n=1$: $3^3+2^0=27+1=28=4\cdot 7$ ✓
2. Neem aan dat $3^{2p+1}+2^{p-1}$ deelbaar is door 7. Dan $3^{2(p+1)+1}+2^p=9\cdot 3^{2p+1}+2\cdot 2^{p-1}=7\cdot 3^{2p+1}+2\left(3^{2p+1}+2^{p-1}\right)$ $7\cdot 3^{2p+1}$ bevat een factor 7, en $2\left(3^{2p+1}+2^{p-1}\right)$ is deelbaar door 7 vanwege de inductiehypothese.
3. Dus $3^{2n+1}+2^{n-1}$ is deelbaar door 7 voor elk natuurlijk getal $n\ge 1$.

Somformule (vergelijk H7 diagnostische toets 8b)

Bewijs dat $\sum _{k=1}^n(4k-1)=2n^2+n$ voor $n\ge 1$.

1. $n=1$: $4-1=3$ en $2+1=3$ ✓
2. Neem aan dat $\sum _{k=1}^p(4k-1)=2p^2+p$. Dan ${\sum }_{k=1}^{p+1}(4k-1)=2p^2+p+4(p+1)-1=2p^2+5p+3=2(p+1{)}^2+(p+1)$
3. Dus de formule geldt voor elk natuurlijk getal $n\ge 1$. ✓ (controle: $2(p+1{)}^2+(p+1)=2p^2+5p+3$)

Valkuilen

• De inductiebasis overslaan of voor de verkeerde $n$ doen (bij "$n\ge 4$" begin je bij 4).
• In stap 2 terugrekenen vanuit wat je wilt bewijzen. Begin bij de linkerkant voor $p+1$.
• Niet expliciet zeggen waar je de inductiehypothese gebruikt.
• De conclusie (stap 3) weglaten.

Test jezelf

Wat is de inductiebasis bij "bewijs dat $9^n-1$ deelbaar is door 8 voor $n\ge 1$"?

$n=1$: $9-1=8$, deelbaar door 8.

Hoe splits je $9^{p+1}-1$ zodat je de hypothese kunt gebruiken?

$9^{p+1}-1=9\cdot 9^p-1=8\cdot 9^p+(9^p-1)$: een achtvoud plus de hypothese.

Oefenen

Goede opgaven om te oefenen

• H7 opgave 36–37 · uitwerking: ongelijkheid en deelbaarheid
• H7 opgave 42–44 · uitwerking: somformules (de uitwerking van 44 staat op de volgende pagina)
• H7 opgave A49 · uitwerking: aantal vlakdelen
• H7 diagnostische toets 8c · uitwerking: somformule vanaf $k=0$
• Gemengde opgave 29 · uitwerking: vier pittige varianten

Bronnen

• §7.3 opgave 35 en Theorie A: Het domino-effect (blz. 117)
• §7.3 Voorbeeld: $3\cdot 2^n>5n+1$ (blz. 118)
• §7.3 Theorie B: Somformules bewijzen (blz. 119)
• §7.3 Voorbeeld: $\sum k^3$ (blz. 120)
• Terugblik §7.3 (blz. 122)
• Diagnostische toets 8 (blz. 135)

---

Ondersteunende onderwerpen

• Definities, vermoedens en stellingen

Onderwerpen die dit ondersteunt

• (geen)