Come si dimostra che una proprietà vale per tutti i numeri naturali, che sono infiniti? Non si possono controllare uno per uno. Il principio di induzione risolve il problema con un'idea semplice: se la proprietà vale per il primo numero, e ogni volta che vale per un numero vale anche per il successivo, allora vale per tutti.
L'idea: una fila di tessere del domino
Immaginate una fila infinita di tessere del domino. Per essere sicuri che cadano tutte bastano due fatti:
- la prima tessera cade;
- ogni tessera, cadendo, fa cadere la successiva.
L'induzione formalizza esattamente questo ragionamento.
La struttura di una dimostrazione per induzione
Sia P(n) una proprietà dei numeri naturali. Per dimostrare che P(n) vale per ogni n ≥ n₀:
- Caso base: si dimostra P(n₀).
- Passo induttivo: si prende un generico k ≥ n₀, si suppone che P(k) sia vera (è l'ipotesi induttiva) e si dimostra P(k + 1).
Il passo induttivo non afferma che P(k) sia vera: dimostra l'implicazione P(k) → P(k + 1). Insieme al caso base, questa implicazione propaga la verità a tutti i numeri.
Primo esempio: la somma dei primi n numeri
Enunciato: per ogni n ≥ 1, 1 + 2 + … + n = n(n + 1)/2.
Caso base (n = 1): il lato sinistro è 1, il destro è 1 · 2 / 2 = 1. Vero.
Passo induttivo: supponiamo che 1 + 2 + … + k = k(k + 1)/2. Allora
1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1)
Raccogliendo (k + 1):
= (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2
che è esattamente la formula con n = k + 1. Dimostrazione completa.
Questa formula ha una conseguenza concreta: un algoritmo con due cicli annidati, in cui il ciclo interno esegue i passi 1, 2, …, n, compie circa n²/2 operazioni, cioè ha complessità quadratica.
Secondo esempio: una disuguaglianza
Enunciato: per ogni n ≥ 4, 2ⁿ ≥ n².
Il caso base non è n = 1 (dove 2 ≥ 1 vale, ma per n = 3 si ha 8 < 9, quindi la proprietà non regge per tutti i valori piccoli). Partiamo da n = 4.
Caso base (n = 4): 2⁴ = 16 e 4² = 16. Vero.
Passo induttivo: supponiamo 2ᵏ ≥ k² con k ≥ 4. Allora 2ᵏ⁺¹ = 2 · 2ᵏ ≥ 2k². Resta da mostrare che 2k² ≥ (k + 1)², cioè k² ≥ 2k + 1. Per k ≥ 4 vale k² ≥ 4k = 2k + 2k ≥ 2k + 8 > 2k + 1. Quindi 2ᵏ⁺¹ ≥ (k + 1)².
L'esempio mostra che la scelta del caso base fa parte della dimostrazione e che nel passo induttivo si può usare l'ipotesi k ≥ n₀.
Terzo esempio: divisibilità
Enunciato: per ogni n ≥ 0, 3 divide n³ − n.
Caso base (n = 0): 0³ − 0 = 0, divisibile per 3.
Passo induttivo: supponiamo che 3 divida k³ − k. Calcoliamo
(k + 1)³ − (k + 1) = k³ + 3k² + 3k + 1 − k − 1 = (k³ − k) + 3(k² + k)
Il primo termine è divisibile per 3 per ipotesi induttiva, il secondo è un multiplo di 3. La somma è divisibile per 3.
Errori tipici
Dimenticare il caso base
Senza caso base si può «dimostrare» qualunque cosa. Esempio: «per ogni n, n = n + 1». Se k = k + 1, sommando 1 si ottiene k + 1 = k + 2: il passo induttivo funziona! Ma non c'è nessun n da cui partire, e l'enunciato è falso.
Un passo induttivo che non vale per tutti i k
Un esempio celebre: «tutti i cavalli hanno lo stesso colore». Caso base: un solo cavallo ha lo stesso colore di sé stesso. Passo: dato un gruppo di k + 1 cavalli, togliendone uno se ne hanno k dello stesso colore; togliendone un altro, altri k dello stesso colore; i due gruppi si sovrappongono, quindi tutti hanno lo stesso colore. L'errore è che per k = 1 i due gruppi sono formati da un solo cavallo ciascuno e non si sovrappongono. Il passo da 1 a 2 fallisce, e tutta la catena crolla.
Usare ciò che si vuole dimostrare
Nel passo induttivo bisogna partire da P(k) e arrivare a P(k + 1), non partire da P(k + 1) e manipolarla fino a ottenere qualcosa di vero, a meno che ogni passaggio sia un'equivalenza.
Induzione e programmazione
L'induzione e la ricorsione sono due facce della stessa idea. Una funzione ricorsiva ha un caso base e un passo che si riconduce a un caso più piccolo; per dimostrare che è corretta si usa quasi sempre l'induzione sulla dimensione dell'input. Se il caso base è giusto e, supponendo che la chiamata ricorsiva restituisca il risultato corretto, il passo costruisce il risultato corretto, allora la funzione è corretta per ogni input.
In sintesi
- L'induzione dimostra P(n) per ogni n ≥ n₀ con un caso base e un passo P(k) → P(k + 1).
- Il caso base va scelto con cura e verificato: senza di esso la dimostrazione non vale.
- Il passo induttivo deve funzionare per ogni k ≥ n₀, compresi i più piccoli.
- È lo strumento naturale per somme, disuguaglianze, divisibilità e formule ricorsive.
- Dimostrare la correttezza di una funzione ricorsiva è, di fatto, una dimostrazione per induzione.
