Volledige inductie

Schrijf bij elke opgave je uitwerking op.

1.
Welke twee delen moet elk bewijs met volledige inductie bevatten?
1. a)Alleen het controleren van de gevallen $n = 1$ tot en met $n = 5$
2. b)Een tegenvoorbeeld en een tegenspraak
3. c)Een basisstap en een inductiestap
4. d)Een tabel met beweringen en redenen
Antwoord: Een basisstap en een inductiestap
Elk inductiebewijs heeft een basisstap (de eerste steen valt) en een inductiestap (elke vallende steen duwt de volgende om) nodig. Een paar gevallen controleren is geen bewijs, en tegenvoorbeelden of tabellen horen bij andere bewijsvormen.
2.
De formule $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ is met inductie bewezen. Controleer haar voor $n = 5$ : wat is $1 + 2 + 3 + 4 + 5$ ?
Antwoord: 15
$1 + 2 + 3 + 4 + 5 = 15$ en $\dfrac{5 \cdot 6}{2} = 15$ . De formule geeft dezelfde waarde.
3.
Controleer $1 + 3 + 5 + \dots + (2n-1) = n^2$ voor $n = 6$ : wat is $1 + 3 + 5 + 7 + 9 + 11$ ?
Antwoord: 36
$1 + 3 + 5 + 7 + 9 + 11 = 36 = 6^2$ , precies zoals de formule voorspelt.
4.
Wat garandeert de inductiestap in het dominobeeld van inductie?
1. a)Alle stenen zijn even groot
2. b)De eerste steen valt
3. c)Elke vallende steen duwt de volgende om
4. d)De laatste steen valt
Antwoord: Elke vallende steen duwt de volgende om
De inductiestap bewijst $P(k) \Rightarrow P(k+1)$ : telkens als een steen valt, valt de volgende ook. Dat de eerste steen valt, is de basisstap. Er is geen laatste steen, de rij is eindeloos.
5.
Controleer de eerste dominostenen voordat je $2^n > n$ bewijst: bereken $2^n$ voor $n = 1, 2, 3$ .
Antwoord: 8
1. Wat is $2^1$ ? (basisstap, vergelijk met $n = 1$ ) 2
2. Wat is $2^2$ ? (vergelijk met $n = 2$ ) 4
3. Wat is $2^3$ ? (vergelijk met $n = 3$ ) 8
6.
Controleer de formule $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ voor $n = 3$ .
Antwoord: 15
1. Bereken de linkerkant $1 + 2 + 4 + 8$ . 15
2. Bereken $2^{3+1} = 2^4$ . 16
3. Bereken de rechterkant $2^4 - 1$ . 15
7.
Zij $P(n)$ de uitspraak $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ . In de inductiestap met $k = 9$ is de rechterkant van $P(k+1)$ gelijk aan $\dfrac{(k+1)(k+2)}{2}$ . Wat is de waarde?
Antwoord: 55
$\dfrac{10 \cdot 11}{2} = 55$ . Controle: de hypothese geeft $1 + \dots + 9 = 45$ , en met de volgende term $10$ erbij krijg je $55$ .
8.
Gebruik de met inductie bewezen formule $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ om $1 + 2 + 4 + 8 + 16 + 32 + 64$ te berekenen.
Antwoord: 127
De laatste term is $2^6$ , dus $n = 6$ en de som is $2^7 - 1 = 128 - 1 = 127$ .
9.
Welke term wordt in de inductiestap voor $1 + 3 + 5 + \dots + (2n-1) = n^2$ bij $1 + 3 + \dots + (2k-1)$ opgeteld om de linkerkant van $P(k+1)$ te krijgen?
1. a) $2k + 1$
2. b) $k + 1$
3. c) $2k$
4. d) $2k - 1$
Antwoord: $2k + 1$
De laatste term van $P(k+1)$ is $2(k+1) - 1 = 2k + 1$ . De term $2k - 1$ zit al in de som, en $k + 1$ en $2k$ zijn niet de oneven getallen van dit patroon.
10.
Volg de inductiestap voor $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ met getallen, met $k = 4$ .
Antwoord: 15
1. Volgens de hypothese is $1 + 2 + 3 + 4 = \dfrac{4 \cdot 5}{2}$ . Hoeveel is dat? 10
2. Wat is de volgende term $k + 1$ ? 5
3. Tel hem op: wat is de nieuwe som $1 + 2 + 3 + 4 + 5$ ? 15
4. Wat geeft de formule voor $k + 1 = 5$ , dus $\dfrac{5 \cdot 6}{2}$ ? 15
11.
Volg de inductiestap voor $1 + 3 + \dots + (2n-1) = n^2$ met getallen, met $k = 6$ .
Antwoord: 49
1. Volgens de hypothese is de som van de eerste $6$ oneven getallen $6^2$ . Hoeveel is dat? 36
2. Wat is het volgende oneven getal $2k + 1$ ? 13
3. Tel het op: wat is de nieuwe som? 49
4. Wat is $(k+1)^2 = 7^2$ ? 49
12.
Welke zin is de juiste inductiehypothese bij het bewijs van $2^n > n$ voor alle $n \ge 1$ ?
1. a)Stel dat $2^n > n$ voor alle $n \ge 1$
2. b)Stel dat $2^k > k$ voor een geheel getal $k \ge 1$
3. c)Stel dat $2^{k+1} > k + 1$
4. d)Bewijs dat $2^1 > 1$
Antwoord: Stel dat $2^k > k$ voor een geheel getal $k \ge 1$
De inductiehypothese neemt de uitspraak aan voor een willekeurige $k$ . Haar aannemen voor alle $n$ of voor $k + 1$ betekent aannemen wat je wilt bewijzen, en $2^1 > 1$ is de basisstap.
13.
De inductiestap voor " $n^3 - n$ is deelbaar door $3$ " gebruikt $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k$ . Controleer dit met $k = 4$ .
Antwoord: 60
1. Wat is $k^3 - k$ voor $k = 4$ ? 60
2. Wat is $(k+1)^3 - (k+1)$ voor $k = 4$ ? 120
3. Wat is het verschil $120 - 60$ ? 60
4. Wat is $3k^2 + 3k$ voor $k = 4$ ? 60
14.
Met inductie kun je ook bewijzen dat $n^3 - n$ deelbaar is door $6$ . Bereken voor $n = 6$ de waarde $\dfrac{6^3 - 6}{6}$ .
Antwoord: 35
$6^3 - 6 = 216 - 6 = 210$ en $210 \div 6 = 35$ , een geheel getal, zoals de uitspraak voorspelt.
15.
Een leerling "bewijst" dat $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ voor alle $n \ge 1$ . De algebra in de inductiestap klopt. Wat is er fout?
1. a)De hypothese moet $P(k+1)$ zijn, niet $P(k)$
2. b)Niets, de uitspraak is waar
3. c)De basisstap faalt: voor $n = 1$ is de linkerkant $1$ en de rechterkant $2$
4. d)Inductie kun je niet gebruiken voor sommen
Antwoord: De basisstap faalt: voor $n = 1$ is de linkerkant $1$ en de rechterkant $2$
Voor $n = 1$ : de linkerkant is $1$ , de rechterkant $\dfrac{1 \cdot 2}{2} + 1 = 2$ . De basisstap faalt, dus de keten start nooit. Sterker nog, de bewering is onwaar voor elke $n$ , want de echte som is $\dfrac{n(n+1)}{2}$ .
16.
Volg de inductiestap voor $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ met getallen, met $k = 5$ .
Antwoord: 127
1. Volgens de hypothese is $1 + 2 + \dots + 2^5 = 2^6 - 1$ . Hoeveel is dat? 63
2. Wat is de volgende term $2^{k+1} = 2^6$ ? 64
3. Tel hem op: wat is de nieuwe som? 127
4. Wat is $2^{k+2} - 1 = 2^7 - 1$ ? 127
17.
De inductiestap voor $2^n > n$ gebruikt de keten $2^{k+1} = 2 \cdot 2^k > 2k \ge k + 1$ . Volg haar met $k = 5$ .
Antwoord: 6
1. Wat is $2^k = 2^5$ ? 32
2. Wat is $2^{k+1} = 2 \cdot 2^5$ ? 64
3. Wat is $2k$ ? 10
4. Wat is $k + 1$ ? 6
18.
De formule $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$ wordt met inductie bewezen. Werk de basisstap en één inductiestap met getallen uit.
Antwoord: 40
1. Basisstap: wat is de rechterkant voor $n = 1$ , dus $\dfrac{1 \cdot 2 \cdot 3}{3}$ ? (De linkerkant is $1 \cdot 2 = 2$ .) 2
2. Hypothese voor $k = 3$ : wat is $\dfrac{3 \cdot 4 \cdot 5}{3}$ ? 20
3. Wat is de volgende term $(k+1)(k+2)$ voor $k = 3$ ? 20
4. Tel hem op bij de waarde van de hypothese. Wat is de nieuwe som? (Vergelijk met $\dfrac{4 \cdot 5 \cdot 6}{3}$ .) 40