Principio di induzione

Scrivi il procedimento per ogni esercizio.

1.
Quali due parti deve contenere ogni dimostrazione per induzione?
1. a)Solo il controllo dei casi da $n = 1$ a $n = 5$
2. b)Un controesempio e una contraddizione
3. c)Un passo base e un passo induttivo
4. d)Una tabella con affermazioni e giustificazioni
Risposta: Un passo base e un passo induttivo
Ogni dimostrazione per induzione ha bisogno di un passo base (cade la prima tessera) e di un passo induttivo (ogni tessera che cade fa cadere la successiva). Controllare qualche caso non è una dimostrazione, e i controesempi o le tabelle appartengono ad altri metodi.
2.
La formula $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ è stata dimostrata per induzione. Verificala per $n = 5$ : quanto fa $1 + 2 + 3 + 4 + 5$ ?
Risposta: 15
$1 + 2 + 3 + 4 + 5 = 15$ e $\dfrac{5 \cdot 6}{2} = 15$ . La formula dà lo stesso valore.
3.
Verifica $1 + 3 + 5 + \dots + (2n-1) = n^2$ per $n = 6$ : quanto fa $1 + 3 + 5 + 7 + 9 + 11$ ?
Risposta: 36
$1 + 3 + 5 + 7 + 9 + 11 = 36 = 6^2$ , proprio come prevede la formula.
4.
Nell'immagine del domino, che cosa garantisce il passo induttivo?
1. a)Tutte le tessere hanno la stessa dimensione
2. b)Cade la prima tessera
3. c)Ogni tessera che cade fa cadere la successiva
4. d)Cade l'ultima tessera
Risposta: Ogni tessera che cade fa cadere la successiva
Il passo induttivo dimostra $P(k) \Rightarrow P(k+1)$ : ogni volta che cade una tessera, cade anche la successiva. La caduta della prima tessera è il passo base. Non esiste un'ultima tessera, la fila è infinita.
5.
Prima di dimostrare $2^n > n$ , controlla le prime tessere: calcola $2^n$ per $n = 1, 2, 3$ .
Risposta: 8
1. Quanto fa $2^1$ ? (passo base, confronta con $n = 1$ ) 2
2. Quanto fa $2^2$ ? (confronta con $n = 2$ ) 4
3. Quanto fa $2^3$ ? (confronta con $n = 3$ ) 8
6.
Verifica la formula $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ per $n = 3$ .
Risposta: 15
1. Calcola il membro sinistro $1 + 2 + 4 + 8$ . 15
2. Calcola $2^{3+1} = 2^4$ . 16
3. Calcola il membro destro $2^4 - 1$ . 15
7.
Sia $P(n)$ l'enunciato $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ . Nel passo induttivo con $k = 9$ , il membro destro di $P(k+1)$ è $\dfrac{(k+1)(k+2)}{2}$ . Quanto vale?
Risposta: 55
$\dfrac{10 \cdot 11}{2} = 55$ . Verifica: l'ipotesi dà $1 + \dots + 9 = 45$ , e aggiungendo il termine successivo $10$ si ottiene $55$ .
8.
Usa la formula $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ , dimostrata per induzione, per calcolare $1 + 2 + 4 + 8 + 16 + 32 + 64$ .
Risposta: 127
L'ultimo termine è $2^6$ , quindi $n = 6$ e la somma è $2^7 - 1 = 128 - 1 = 127$ .
9.
Nel passo induttivo per $1 + 3 + 5 + \dots + (2n-1) = n^2$ , quale termine si aggiunge a $1 + 3 + \dots + (2k-1)$ per ottenere il membro sinistro di $P(k+1)$ ?
1. a) $2k + 1$
2. b) $k + 1$
3. c) $2k$
4. d) $2k - 1$
Risposta: $2k + 1$
L'ultimo termine di $P(k+1)$ è $2(k+1) - 1 = 2k + 1$ . Il termine $2k - 1$ è già nella somma, e $k + 1$ e $2k$ non sono i dispari di questo schema.
10.
Segui il passo induttivo per $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ con i numeri, usando $k = 4$ .
Risposta: 15
1. Per l'ipotesi, $1 + 2 + 3 + 4 = \dfrac{4 \cdot 5}{2}$ . Quanto fa? 10
2. Qual è il termine successivo $k + 1$ ? 5
3. Aggiungilo: qual è la nuova somma $1 + 2 + 3 + 4 + 5$ ? 15
4. Che cosa dà la formula per $k + 1 = 5$ , cioè $\dfrac{5 \cdot 6}{2}$ ? 15
11.
Segui il passo induttivo per $1 + 3 + \dots + (2n-1) = n^2$ con i numeri, usando $k = 6$ .
Risposta: 49
1. Per l'ipotesi, la somma dei primi $6$ dispari è $6^2$ . Quanto fa? 36
2. Qual è il dispari successivo $2k + 1$ ? 13
3. Aggiungilo: qual è la nuova somma? 49
4. Quanto fa $(k+1)^2 = 7^2$ ? 49
12.
Quale frase è l'ipotesi induttiva corretta per dimostrare $2^n > n$ per ogni $n \ge 1$ ?
1. a)Supponiamo $2^n > n$ per ogni $n \ge 1$
2. b)Supponiamo $2^k > k$ per un certo intero $k \ge 1$
3. c)Supponiamo $2^{k+1} > k + 1$
4. d)Dimostrare che $2^1 > 1$
Risposta: Supponiamo $2^k > k$ per un certo intero $k \ge 1$
L'ipotesi induttiva suppone l'enunciato per un $k$ qualsiasi. Supporlo per ogni $n$ o per $k + 1$ significa supporre ciò che vogliamo dimostrare, e $2^1 > 1$ è il passo base.
13.
Il passo induttivo per " $n^3 - n$ è divisibile per $3$ " usa $(k+1)^3 - (k+1) = (k^3 - k) + 3k^2 + 3k$ . Verificalo con $k = 4$ .
Risposta: 60
1. Quanto fa $k^3 - k$ per $k = 4$ ? 60
2. Quanto fa $(k+1)^3 - (k+1)$ per $k = 4$ ? 120
3. Quanto fa la differenza $120 - 60$ ? 60
4. Quanto fa $3k^2 + 3k$ per $k = 4$ ? 60
14.
Per induzione si può anche dimostrare che $n^3 - n$ è divisibile per $6$ . Per $n = 6$ , calcola $\dfrac{6^3 - 6}{6}$ .
Risposta: 35
$6^3 - 6 = 216 - 6 = 210$ e $210 \div 6 = 35$ , un numero intero, come prevede l'enunciato.
15.
Uno studente "dimostra" che $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ per ogni $n \ge 1$ . L'algebra del passo induttivo è corretta. Che cosa non va?
1. a)L'ipotesi deve essere $P(k+1)$ , non $P(k)$
2. b)Niente, l'enunciato è vero
3. c)Il passo base fallisce: per $n = 1$ il membro sinistro è $1$ , quello destro è $2$
4. d)L'induzione non si può usare per le somme
Risposta: Il passo base fallisce: per $n = 1$ il membro sinistro è $1$ , quello destro è $2$
Per $n = 1$ : il membro sinistro è $1$ , quello destro $\dfrac{1 \cdot 2}{2} + 1 = 2$ . Il passo base fallisce, quindi la catena non parte mai. Infatti l'affermazione è falsa per ogni $n$ , perché la vera somma è $\dfrac{n(n+1)}{2}$ .
16.
Segui il passo induttivo per $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ con i numeri, usando $k = 5$ .
Risposta: 127
1. Per l'ipotesi, $1 + 2 + \dots + 2^5 = 2^6 - 1$ . Quanto fa? 63
2. Qual è il termine successivo $2^{k+1} = 2^6$ ? 64
3. Aggiungilo: qual è la nuova somma? 127
4. Quanto fa $2^{k+2} - 1 = 2^7 - 1$ ? 127
17.
Il passo induttivo per $2^n > n$ usa la catena $2^{k+1} = 2 \cdot 2^k > 2k \ge k + 1$ . Seguila con $k = 5$ .
Risposta: 6
1. Quanto fa $2^k = 2^5$ ? 32
2. Quanto fa $2^{k+1} = 2 \cdot 2^5$ ? 64
3. Quanto fa $2k$ ? 10
4. Quanto fa $k + 1$ ? 6
18.
La formula $1 \cdot 2 + 2 \cdot 3 + \dots + n(n+1) = \dfrac{n(n+1)(n+2)}{3}$ si dimostra per induzione. Svolgi il suo passo base e un passo induttivo con i numeri.
Risposta: 40
1. Passo base: quanto vale il membro destro per $n = 1$ , cioè $\dfrac{1 \cdot 2 \cdot 3}{3}$ ? (Il membro sinistro è $1 \cdot 2 = 2$ .) 2
2. Ipotesi per $k = 3$ : quanto fa $\dfrac{3 \cdot 4 \cdot 5}{3}$ ? 20
3. Qual è il termine successivo $(k+1)(k+2)$ per $k = 3$ ? 20
4. Aggiungilo al valore dell'ipotesi. Qual è la nuova somma? (Confronta con $\dfrac{4 \cdot 5 \cdot 6}{3}$ .) 40