Somma dei primi n interi positivi

Dimostra che $1 + 2 + 3 + \dots + n = \dfrac{n(n+1)}{2}$ per ogni $n \ge 1$.

Passo base: verifica $n = 1$: Membro sinistro: $1$. Membro destro: $\dfrac{1 \cdot 2}{2} = 1$ = $P(1)$ è vero

Ipotesi induttiva: supponi $P(k)$ per un certo $k \ge 1$: Supponiamo che $1 + 2 + \dots + k = \dfrac{k(k+1)}{2}$ = Possiamo usare questa uguaglianza

Passo induttivo: aggiungi il termine successivo $k+1$ a entrambi i membri: $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}$

Confronta con $P(k+1)$: $P(k+1)$ afferma che la somma è uguale a $\dfrac{(k+1)\big((k+1)+1\big)}{2} = \dfrac{(k+1)(k+2)}{2}$ = $P(k+1)$ è vero

Answer: Per induzione, $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ per ogni $n \ge 1$. Per esempio, $1 + 2 + \dots + 100 = \dfrac{100 \cdot 101}{2} = 5050$.

Somma dei primi n numeri dispari

Dimostra che $1 + 3 + 5 + \dots + (2n-1) = n^2$ per ogni $n \ge 1$.

Passo base: verifica $n = 1$: Membro sinistro: $1$. Membro destro: $1^2 = 1$ = $P(1)$ è vero

Ipotesi induttiva: Supponiamo che $1 + 3 + \dots + (2k-1) = k^2$ per un certo $k \ge 1$ = Possiamo usare questa uguaglianza

Trova il dispari successivo: Il numero dispari dopo $2k-1$ è $2(k+1) - 1 = 2k + 1$ = Aggiungiamo $2k + 1$

Passo induttivo: $1 + 3 + \dots + (2k-1) + (2k+1) = k^2 + 2k + 1$ = $= (k+1)^2$, quindi $P(k+1)$ è vero

Answer: Per induzione, la somma dei primi $n$ numeri dispari è $n^2$. Verifica: $1 + 3 + 5 + 7 + 9 = 25 = 5^2$.

Somma delle potenze di 2

Dimostra che $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ per ogni $n \ge 0$.

Passo base: qui il primo valore è $n = 0$: Membro sinistro: $2^0 = 1$. Membro destro: $2^{1} - 1 = 1$ = $P(0)$ è vero

Ipotesi induttiva: Supponiamo che $1 + 2 + \dots + 2^k = 2^{k+1} - 1$ per un certo $k \ge 0$ = Possiamo usare questa uguaglianza

Passo induttivo: aggiungi il termine successivo $2^{k+1}$: $1 + 2 + \dots + 2^k + 2^{k+1} = 2^{k+1} - 1 + 2^{k+1}$ = $= 2 \cdot 2^{k+1} - 1$

Semplifica e confronta con $P(k+1)$: $2 \cdot 2^{k+1} - 1 = 2^{k+2} - 1 = 2^{(k+1)+1} - 1$ = $P(k+1)$ è vero

Answer: Per induzione, $1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$ per ogni $n \ge 0$. Verifica per $n = 6$: $1 + 2 + 4 + 8 + 16 + 32 + 64 = 127 = 2^7 - 1$.

Una dimostrazione di divisibilità

Dimostra che $n^3 - n$ è divisibile per $3$ per ogni $n \ge 1$. (La lezione Dimostrazione diretta lo ha mostrato scomponendo; ora usiamo l'induzione.)

Passo base: verifica $n = 1$: $1^3 - 1 = 0 = 3 \cdot 0$ = $P(1)$ è vero

Ipotesi induttiva: Supponiamo che $k^3 - k = 3m$ per un certo intero $m$ = $k^3 - k$ è un multiplo di $3$

Sviluppa l'espressione per $k+1$: $(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$ = $= (k^3 - k) + 3k^2 + 3k$

Usa l'ipotesi induttiva: $(k^3 - k) + 3k^2 + 3k = 3m + 3(k^2 + k)$ = $= 3(m + k^2 + k)$

Concludi: $m + k^2 + k$ è un intero, quindi l'espressione è un multiplo di $3$ = $P(k+1)$ è vero

Answer: Per induzione, $3$ divide $n^3 - n$ per ogni $n \ge 1$. Verifica per $n = 5$: $125 - 5 = 120 = 3 \cdot 40$.

Una disuguaglianza: 2 elevato alla n è maggiore di n

Dimostra che $2^n > n$ per ogni $n \ge 1$.

Passo base: verifica $n = 1$: $2^1 = 2$ e $2 > 1$ = $P(1)$ è vero

Ipotesi induttiva: Supponiamo che $2^k > k$ per un certo $k \ge 1$ = Possiamo usare questa disuguaglianza

Scrivi $2^{k+1}$ usando $2^k$: $2^{k+1} = 2 \cdot 2^k > 2 \cdot k$ = $2^{k+1} > 2k$

Confronta $2k$ con $k+1$: $2k = k + k \ge k + 1$, perché $k \ge 1$ = $2k \ge k + 1$

Concatena le disuguaglianze: $2^{k+1} > 2k \ge k + 1$ = $2^{k+1} > k + 1$, quindi $P(k+1)$ è vero

Answer: Per induzione, $2^n > n$ per ogni $n \ge 1$. Per esempio, $2^{10} = 1024 > 10$.

Mistake: Saltare il passo base

Why: Il passo induttivo da solo non dimostra nulla: dice solo che SE cade una tessera, cade anche la successiva. Esempio: l'affermazione falsa $1 + 2 + \dots + n = \dfrac{n(n+1)}{2} + 1$ ha un passo induttivo che funziona, ma per $n = 1$ il membro sinistro è $1$ e quello destro è $2$.

Correct: Verifica sempre il primo caso in modo esplicito. Senza una prima tessera che cade, non cade niente.

Mistake: Supporre ciò che vuoi dimostrare

Why: Scrivere "supponiamo $P(n)$ vero per ogni $n$" oppure "supponiamo $P(k+1)$" è un ragionamento circolare: si suppone la tesi.

Correct: Supponi $P(k)$ per UN valore $k$ (l'ipotesi induttiva) e dimostra $P(k+1)$ a partire da essa.

Mistake: Algebra sbagliata nel passo induttivo

Why: Una svista frequente è aggiungere il termine successivo sbagliato, per esempio $2k - 1$ invece di $2k + 1$ nella somma dei dispari, oppure dimenticare di aggiungere il nuovo termine in un membro.

Correct: Scrivi prima $P(k+1)$ per intero (sostituisci ogni $n$ con $k+1$), poi lavora per arrivare esattamente a quell'espressione.

Mistake: Credere che controllare molti casi sia una dimostrazione

Why: L'espressione $n^2 + n + 41$ dà numeri primi per $n = 0, 1, \dots, 39$, ma per $n = 40$ dà $1681 = 41^2$, che non è primo.

Correct: Gli esempi aiutano a intuire una formula. Solo il passo base insieme al passo induttivo la dimostrano per ogni $n$.

Verificare i programmi per computer

I programmatori usano l'induzione per dimostrare che un ciclo dà la risposta giusta dopo qualsiasi numero di giri: se è giusta dopo $k$ giri, è giusta anche dopo $k+1$ giri.

Un ciclo aggiunge $1, 2, 3, \dots$ a un totale. L'induzione dimostra che dopo $n$ giri il totale è $\dfrac{n(n+1)}{2}$.

La Torre di Hanoi

In questo rompicapo sposti una pila di dischi su un altro paletto, un disco alla volta, senza mai mettere un disco più grande sopra uno più piccolo. L'induzione dimostra che $n$ dischi richiedono $2^n - 1$ mosse.

Per spostare $k+1$ dischi, sposti via i $k$ dischi in alto, poi il disco più grande, poi rimetti sopra i $k$ dischi: $2(2^k - 1) + 1 = 2^{k+1} - 1$ mosse.

I chicchi di riso sulla scacchiera

Un'antica leggenda: metti $1$ chicco di riso sulla prima casella, $2$ sulla seconda, $4$ sulla terza, raddoppiando ogni volta. La somma delle potenze di 2 ti dà il totale.

Sulle prime $3$ caselle ci sono $1 + 2 + 4 = 7 = 2^3 - 1$ chicchi.

Q: Perché l'induzione dimostra davvero l'enunciato per OGNI n?

A: Il passo base dà $P(1)$. Il passo induttivo con $k = 1$ dà $P(2)$, con $k = 2$ dà $P(3)$, e così via. Ogni intero positivo viene raggiunto dopo un numero finito di passi, quindi nessun $n$ resta escluso.

Q: Il passo base deve essere sempre n = 1?

A: No. Parti dal primo valore a partire dal quale l'enunciato deve valere. La somma delle potenze di 2 parte da $n = 0$. L'enunciato $2^n > n^2$ è falso per $n = 2, 3, 4$ (per esempio $2^4 = 16 = 4^2$) ed è vero per ogni $n \ge 5$, quindi quella dimostrazione usa il passo base $n = 5$.

Q: Il principio di induzione è la stessa cosa del ragionamento induttivo delle scienze?

A: No. Il ragionamento induttivo intuisce una regola generale dagli esempi e può sbagliare. Il principio di induzione è una dimostrazione deduttiva: una volta dimostrati il passo base e il passo induttivo, il risultato è certo.

Q: Che cos'è l'induzione forte?

A: Nell'induzione forte l'ipotesi suppone che $P(1), P(2), \dots, P(k)$ siano tutti veri, non solo $P(k)$. È utile quando $P(k+1)$ dipende da più casi precedenti, per esempio nelle dimostrazioni sulla scomposizione in fattori primi.