Principio di induzione

Nome:

Classe:

Data:

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
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$ ?
3.
Verifica $1 + 3 + 5 + \dots + (2n-1) = n^2$ per $n = 6$ : quanto fa $1 + 3 + 5 + 7 + 9 + 11$ ?
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
5.
Prima di dimostrare $2^n > n$ , controlla le prime tessere: calcola $2^n$ per $n = 1, 2, 3$ .
6.
Verifica la formula $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ per $n = 3$ .
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?
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$ .
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$
10.
Segui il passo induttivo per $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ con i numeri, usando $k = 4$ .
11.
Segui il passo induttivo per $1 + 3 + \dots + (2n-1) = n^2$ con i numeri, usando $k = 6$ .
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$
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$ .
14.
Per induzione si può anche dimostrare che $n^3 - n$ è divisibile per $6$ . Per $n = 6$ , calcola $\dfrac{6^3 - 6}{6}$ .
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
16.
Segui il passo induttivo per $1 + 2 + \dots + 2^n = 2^{n+1} - 1$ con i numeri, usando $k = 5$ .
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$ .
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.