Principio di induzione (da zero)

Esercizi svolti: gli esercizi della prof (lezione 3) Esercizio 10 - somma dei primi n numeri per induzione, Esercizio 11 - disuguaglianza di Bernoulli, Esercizio 12 - binomio di Newton per induzione; inoltre Esercizio 5 - 2^n maggiore di n per induzione e Esercizio 6 - numero di sottoinsiemi (insieme delle parti).

A che cosa serve

Molte affermazioni in matematica parlano di tutti i numeri naturali. Per esempio:

"Per ogni $n \in \mathbb{N}$ vale $2^n > n$."

I naturali sono infiniti. Controllare l'affermazione a mano per $n = 0, 1, 2, 3, \dots$ non finirebbe mai, e, peggio, non dimostrerebbe nulla: potrebbe fallire per un $n$ enorme che non abbiamo provato. Serve un metodo che dimostri l'affermazione per tutti gli $n$ in un colpo solo, con un numero finito di passaggi. Questo metodo è l'induzione.

L'idea: le tessere del domino

Immagina una fila infinita di tessere del domino, numerate $0, 1, 2, 3, \dots$ Vuoi dimostrare che cadono tutte. Ti bastano due cose:

1. La prima tessera cade (la tessera $0$: qualcuno la spinge).
2. Se una tessera qualsiasi cade, allora cade anche la successiva. (Le tessere sono messe abbastanza vicine.)

Con queste due cose cadono tutte: la $0$ cade per la regola 1; siccome la $0$ cade, per la regola 2 cade la $1$; siccome cade la $1$, cade la $2$; e così via, senza fine. Nessuna tessera può restare in piedi, perché per cadere ognuna aspetta solo che sia caduta la precedente.

Nella dimostrazione per induzione:

• "la tessera $n$ cade" = "l'affermazione è vera per $n$";
• la regola 1 si chiama passo base;
• la regola 2 si chiama passo induttivo.

Come si scrive una dimostrazione per induzione

Chiamiamo $P(n)$ l'affermazione che dipende da $n$ (per esempio $P(n)$: "$2^n > n$"). Vogliamo dimostrare che $P(n)$ è vera per ogni $n \ge n_0$ (di solito $n_0 = 0$ o $n_0 = 1$).

1. Passo base

Si verifica $P(n_0)$ sostituendo il valore iniziale e controllando che l'affermazione sia vera. È un semplice conto.

2. Passo induttivo

Si dimostra l'implicazione: "se $P(n)$ è vera per un certo $n$, allora è vera anche $P(n+1)$".

• Si suppone che $P(n)$ sia vera per un $n$ fissato. Questa supposizione si chiama ipotesi induttiva. Non è un'assurdità né un ragionamento circolare: non stiamo dicendo che $P(n)$ sia vera, stiamo solo dicendo "se lo fosse, allora…".
• Si scrive cosa bisogna dimostrare, cioè $P(n+1)$. Questa si chiama tesi del passo induttivo.
• Si dimostra la tesi, e in qualche punto del ragionamento si usa l'ipotesi induttiva. Se non la si usa mai, quasi certamente c'è un errore (si starebbe dimostrando $P(n+1)$ da zero, senza bisogno dell'induzione).

3. Conclusione

Per il principio di induzione, $P(n)$ vale per ogni $n \ge n_0$.

Perché funziona

Il passo base garantisce $P(n_0)$. Il passo induttivo, applicato con $n = n_0$, dà $P(n_0 + 1)$; applicato con $n = n_0 + 1$, dà $P(n_0 + 2)$; e così via. Ogni numero naturale si raggiunge dopo un numero finito di passi a partire da $n_0$, quindi nessun naturale può "sfuggire". Questa è proprio una proprietà che caratterizza i numeri naturali: si ottengono tutti partendo da $0$ e aggiungendo $1$ ripetutamente.

L'enunciato come teorema (versione della prof)

Teorema (principio di induzione). Sia $n_0 \in \mathbb{N}$ e sia $p(n)$ un predicato sui naturali. La proposizione "$\forall n \ge n_0 : p(n)$" è vera se e solo se

1. $p(n_0)$ è vera;
2. $p(n) \Rightarrow p(n+1)$ per ogni $n \ge n_0$ (cioè: per un $n \ge n_0$ fissato generico, supponendo vera $p(n)$, si dimostra che è vera anche $p(n+1)$).

Il teorema si basa su due proprietà dei naturali: ogni $n \in \mathbb{N}$ ha un successivo $n + 1 \in \mathbb{N}$, e ogni $n \in \mathbb{N}^*$ ha un precedente $n - 1 \in \mathbb{N}$.

Dimostrazione

È un "se e solo se", quindi si dimostrano le due implicazioni.

"$\Rightarrow$" (facile). Supponiamo che $p(n)$ sia vera per ogni $n \ge n_0$. Allora:

1. in particolare è vera $p(n_0)$;
2. per ogni $n \ge n_0$ sono vere sia $p(n)$ sia $p(n+1)$, e un'implicazione tra due proposizioni vere è vera (tabella di verità in Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori →). Quindi $p(n) \Rightarrow p(n+1)$.

"$\Leftarrow$" (la parte importante, per assurdo). Supponiamo vere 1 e 2, e supponiamo per assurdo che "$\forall n \ge n_0 : p(n)$" sia falsa. Negando il "per ogni": esiste $\bar{n} \in \mathbb{N}$, $\bar{n} \ge n_0$, con $p(\bar{n})$ falsa.

• $\bar{n} \ne n_0$, perché $p(n_0)$ è vera per la 1. Quindi $\bar{n} > n_0$, e dunque $\bar{n} - 1 \ge n_0$ (è ancora un naturale nel nostro intervallo).
• Anche $p(\bar{n} - 1)$ è falsa. Infatti, se fosse vera, la 2 (applicata con $n = \bar{n} - 1$) darebbe vera $p((\bar{n} - 1) + 1) = p(\bar{n})$, che invece è falsa.
• Ripetendo lo stesso ragionamento si ha una catena: $p(\bar{n})$ falsa $\Rightarrow$ $p(\bar{n} - 1)$ falsa $\Rightarrow$ $p(\bar{n} - 2)$ falsa $\Rightarrow \dots$ Scendendo di $1$ alla volta, dopo $\bar{n} - n_0$ passi (un numero finito) si arriva a $p(n_0)$ falsa.

Ma per la 1, $p(n_0)$ è vera: contraddizione ⚡. Quindi $p(n)$ è vera per ogni $n \ge n_0$ ∎.

Utilità del principio di induzione

• Nelle dimostrazioni: riduce una dimostrazione con infiniti casi ("per ogni $n$") a due passi di dimostrazione.
• Nelle definizioni per ricorrenza: permette di definire un oggetto per ogni $n$ dicendo solo chi è il primo e come si passa da uno al successivo. Esempio, il fattoriale (vedi Fattoriale e coefficienti binomialiFattoriale, permutazioni, disposizioni, combinazioni e coefficiente binomiale n su k, con il triangolo di Tartaglia.Fattoriale e coefficienti binomiali →): $$0! = 1 \quad (\text{il caso } n = 0), \qquad (n+1)! = (n+1) \cdot n! \quad (\text{il passaggio da } n \text{ a } n+1)$$ Da qui: $1! = 1 \cdot 0! = 1$, $2! = 2 \cdot 1! = 2$, $3! = 3 \cdot 2! = 6$, e così via per ogni $n$.

Un primo esempio completo (piccolo)

(È l'esercizio 1 della prof sull'induzione; la versione con tutti i commenti è nell'Esercizio 10 - somma dei primi n numeri per induzione.)

Affermazione. Per ogni $n \ge 1$:

$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$

Passo base ($n = 1$). A sinistra c'è solo $1$. A destra: $\frac{1 \cdot 2}{2} = 1$. Sono uguali ✓.

Passo induttivo. Fissiamo $n \ge 1$.

• Ipotesi induttiva: $1 + 2 + \dots + n = \frac{n(n+1)}{2}$.
• Tesi: $1 + 2 + \dots + n + (n+1) = \frac{(n+1)(n+2)}{2}$ (è la stessa formula con $n+1$ al posto di $n$).
• Dimostrazione. Nel membro di sinistra della tesi, i primi $n$ addendi formano la somma dell'ipotesi, che sappiamo valere $\frac{n(n+1)}{2}$. Quindi:

$$1 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2} + 1\right) = (n+1) \cdot \frac{n+2}{2} = \frac{(n+1)(n+2)}{2}$$

Ed è proprio la tesi ✓.

Conclusione. La formula vale per ogni $n \ge 1$.

Si noti dove è stata usata l'ipotesi induttiva: nel sostituire $1 + \dots + n$ con $\frac{n(n+1)}{2}$. È il momento chiave di ogni dimostrazione per induzione.

Induzione che parte da un valore diverso da 0

Se l'affermazione è richiesta solo per $n \ge n_0$, il passo base si fa per $n = n_0$ (per esempio $n_0 = 1$ o $n_0 = 5$) e il passo induttivo si dimostra per $n \ge n_0$. È come far partire il domino da una tessera diversa.

Errori comuni

• Dimenticare il passo base. Senza la prima tessera spinta, il domino non parte. (Esempio: "$n = n + 1$" ha un passo induttivo che sembra funzionare, ma è falsa per ogni $n$ perché non esiste nessun passo base valido.)
• Dimostrare solo il passo base e fermarsi: verificare qualche caso non basta.
• Usare la tesi per dimostrare la tesi (ragionamento circolare), invece dell'ipotesi induttiva.
• Non usare mai l'ipotesi induttiva nel passo induttivo.
• Confondere $n$ e $n+1$: nella tesi bisogna sostituire $n+1$ ovunque compaia $n$ nell'affermazione, con attenzione alle parentesi.
• Passo induttivo che non vale per il primo valore: controllare che l'argomento funzioni per tutti gli $n \ge n_0$, compreso il primo.