Dimostrazioni per induzione
Sul tuo smartphone c'è una fila di tessere del domino: se ne cade una, fa cadere la successiva. Basta far cadere la prima e cadranno tutte, anche se sono infinite. Ma come si dimostra che una formula vale per tutti i numeri naturali, se non possiamo provarli uno a uno? Il principio di induzione risponde proprio a questa domanda.
L'idea: il domino e il principio di induzione
Considera la formula $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$. Per $n = 1$ vale, per $n = 2$ vale, per $n = 5$ pure. Ma verificare qualche caso non è una dimostrazione: non sappiamo se la formula vale anche per $n = 1000$.
L'induzione funziona come il domino. Servono due cose:
-
la prima tessera cade (passo base);
-
ogni tessera che cade fa cadere la successiva (passo induttivo).
Nel passo induttivo la proprietà $P(n)$ che si assume vera si chiama ipotesi induttiva; la proprietà $P(n+1)$ che si vuole ottenere si chiama tesi induttiva. Il perché della regola è il domino: dal passo base ricavi $P(n_0)$, dal passo induttivo ricavi $P(n_0+1)$, poi $P(n_0+2)$, e così via senza fine.
Verifica che la formula $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ è vera per $n = 1$, $n = 2$ e $n = 5$.
Verifica che la formula $1 + 2 + \dots + n = \dfrac{n(n+1)}{2}$ è vera per $n = 1$, $n = 2$ e $n = 5$.
Per la proprietà $P(n)$: «$2^n > n$», scrivi il passo base per $n = 1$ e l'enunciato dell'ipotesi induttiva e della tesi induttiva per il passo $n \to n+1$.
Per la proprietà $P(n)$: «$2^n > n$», scrivi il passo base per $n = 1$ e l'enunciato dell'ipotesi induttiva e della tesi induttiva per il passo $n \to n+1$.
Come si scrive una dimostrazione per induzione
Uno schema da seguire sempre, scritto per esteso:
-
enuncia $P(n)$ e scegli $n_0$;
-
passo base: verifica $P(n_0)$ con un calcolo;
-
ipotesi induttiva: scrivi $P(n)$ e supponila vera per un certo $n \ge n_0$;
-
tesi induttiva: scrivi cosa vuoi ottenere, cioè $P(n+1)$;
-
dimostrazione: parti da un membro di $P(n+1)$ e usa l'ipotesi induttiva per arrivare all'altro;
-
concludi per il principio di induzione.
Calcola la somma dei primi 6 numeri dispari e verifica che coincide con $6^2$.
Calcola la somma dei primi 6 numeri dispari e verifica che coincide con $6^2$.
Dimostra per induzione che per ogni $n \ge 1$: $1 + 3 + 5 + \dots + (2n-1) = n^2$
Dimostra per induzione che per ogni $n \ge 1$:
$1 + 3 + 5 + \dots + (2n-1) = n^2$
Somme e divisibilità
Lo stesso schema vale per altre somme (quella dei quadrati, dei dispari…) e per le proprietà di divisibilità. In quest'ultimo caso il trucco è far comparire l'ipotesi induttiva riscrivendo il termine con $n+1$.
Per la somma dei quadrati l'idea è identica a quella della somma dei primi $n$ numeri: nel passo induttivo si aggiunge il termine $(n+1)^2$ a $\dfrac{n(n+1)(2n+1)}{6}$ e si raccoglie $(n+1)$ a fattore comune.
Dimostra per induzione che per ogni $n \ge 1$ il numero $4^n - 1$ è divisibile per 3.
Dimostra per induzione che per ogni $n \ge 1$ il numero $4^n - 1$ è divisibile per 3.
Dimostra per induzione che per ogni $n \ge 1$: $1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$
Dimostra per induzione che per ogni $n \ge 1$:
$1^2 + 2^2 + \dots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$
Disuguaglianze e passo base diverso da 1
Il principio vale a partire da qualsiasi $n_0$. Per le disuguaglianze capita spesso che la proprietà sia falsa per i primi valori e diventi vera solo da un certo $n_0$ in poi. Il passo base si fa allora su quel $n_0$.
Esempio: $2^n > n^2$. Per $n = 1$: $2 > 1$ vera. Per $n = 2$: $4 > 4$ falsa. Per $n = 3$: $8 > 9$ falsa. Per $n = 4$: $16 > 16$ falsa. Per $n = 5$: $32 > 25$ vera.
Nelle disuguaglianze la catena è: ipotesi induttiva $\Rightarrow$ una prima disuguaglianza $\Rightarrow$ una seconda più semplice da controllare $\Rightarrow$ la tesi.
Dimostra per induzione che $2^n > n^2$ per ogni intero $n \ge 5$. Spiega perché il passo base non può essere $n=1$.
Dimostra per induzione che $2^n > n^2$ per ogni intero $n \ge 5$. Spiega perché il passo base non può essere $n=1$.
Dimostra per induzione la disuguaglianza di Bernoulli: per $x > -1$ e ogni intero $n \ge 1$ vale $(1+x)^n \ge 1 + nx$.
Dimostra per induzione la disuguaglianza di Bernoulli: per $x > -1$ e ogni intero $n \ge 1$ vale $(1+x)^n \ge 1 + nx$.
Quando l'induzione sembra funzionare… ma non funziona
Il passo base e il passo induttivo sono entrambi necessari e il secondo deve valere per ogni $n \ge n_0$, compreso il primo.
Un caso famoso è il «paradosso dei cavalli»: si "dimostra" che tutti i cavalli di un gruppo hanno lo stesso colore. Il passo base ($n=1$) è vero. Nel passo induttivo si considerano $n+1$ cavalli: togliendone uno restano $n$ cavalli con lo stesso colore; togliendone un altro idem. I due gruppi di $n$ cavalli hanno in comune $n - 1$ cavalli, e da questo si conclude che tutti i cavalli hanno lo stesso colore.
Considera la «dimostrazione» seguente: «Tutti i cavalli di un gruppo di $n$ cavalli hanno lo stesso colore». Base: $n=1$ vera. Passo: dati $n+1$ cavalli, togliendone uno…
Considera la «dimostrazione» seguente: «Tutti i cavalli di un gruppo di $n$ cavalli hanno lo stesso colore». Base: $n=1$ vera. Passo: dati $n+1$ cavalli, togliendone uno i restanti $n$ hanno lo stesso colore; togliendone un altro idem; quindi tutti hanno lo stesso colore. Individua l'errore nel passo induttivo e spiega per quale valore di $n$ il ragionamento fallisce.
In sintesi
-
Principio di induzione: se $P(n_0)$ è vera (passo base) e da $P(n)$ segue $P(n+1)$ per ogni $n \ge n_0$ (passo induttivo), allora $P(n)$ vale per ogni $n \ge n_0$.
-
Schema: passo base → ipotesi induttiva → tesi induttiva → dimostrazione → conclusione.
-
Nel passo induttivo parti da un membro della tesi e usa l'ipotesi: non partire dalla tesi stessa.
-
Per le divisibilità riscrivi $a^{n+1} = a \cdot a^n$ e sostituisci l'ipotesi; per le somme raccogli il fattore comune.
-
Per le disuguaglianze il passo base può essere $n_0 > 1$; il passo induttivo deve funzionare da $n_0$ in poi.
-
Passo base e passo induttivo sono entrambi indispensabili.