Il principio di induzione: teoria

Principio di Induzione in Analisi Matematica

Home » Il principio di induzione: teoria

Il principio di induzione è un concetto fondamentale della Matematica.

Esso può essere paragonato alle tessere del domino: per assicurarsi che cadano tutte, basta spingere la prima (detto passo base) ed essere certi che, assumendo che una generica tessera cada, tale caduta implichi la caduta della successiva (detto passo induttivo).

In maniera analoga, per verificare che una proprietà sia valida per ogni numero naturale basta assicurarsi che lo $0$ , il primo numero naturale, ne goda (passo base) e che, assumendo la proprietà vera per un generico numero $n$ , ciò implichi la validità della proprietà per il numero successivo $n+1$ (passo induttivo).

Questo semplice e potente strumento consente di affrontare numerosi problemi dell’aritmetica.

In questo articolo presentiamo la forma semplice, generalizzata e forte del principio di induzione e ci dedichiamo soprattutto all’analisi di esempi applicativi: la formula per la somma dei primi numeri naturali, il rompicapo della torre di Hanoi, la disuguaglianza di Bernoulli e il Teorema Fondamentale dell’Aritmetica.

Se desideri approfondire la conoscenza di questo fondamentale strumento della Matematica, continua pure la lettura!

Autori e revisori

Leggi...

Autore: Daniele Fakhoury

Revisore: Valerio Brunetti.

Principio 1 (induzione). Sia $P(n)$ una proposizione sui numeri naturali, se

$P(0)$ è verificata (passo base);
$\forall n\in \mathbb{N}, \; P(n) \Rightarrow P(n+1)$ (passo induttivo).

allora $P(n)$ è vera $\forall n \in \mathbb{N}$ .

In altri termini, per dimostrare che una certa proposizione sui numeri naturali sempre è vera ( $P(n)$ è vera $\forall n \in \mathbb{N}$ ) è sufficiente dimostrare che

la proposizione è vera se poniamo $n = 0$ (il passo base);
data per vera $P(n)$ (ipotesi induttiva), riusciamo a dimostrare che la proposizione è vera anche per $n+1$ .

Per ricordare questo principio è utile pensare alla metafora di una infinità di tessere del domino disposte lungo una fila. La proposizione $P(n)$ in questo caso può essere formulata come “l’ennesima tessere del domino cade”. Invece di controllare ad una ad una se le tessere del domino cascano o meno (cosa che non possiamo fare perché sono infinite) ci basta osservare

se la prima tessera del domino è caduta (passo base);
e se (per ogni $n$ ) l’ $n$ -esima tessera cade (ipotesi induttiva), questa fa cadere l’ $(n+1)$ -esima tessera del domino.

Se queste due condizioni sono verificate, possiamo star certi che cadranno tutte le tessere del domino e possiamo dormire sereni senza doverle controllare tutte. Infatti, osservando che la prima cade (passo base), per ipotesi induttiva, sappiamo che la seconda cade (sappiamo che $P(n) \Rightarrow P(n+1)$ ), ma se la seconda cade allora…

Ma cosa succede se la prima tessera del domino non cade (non vale il passo base per $n=0$ )? Magari è incollata al pavimento, o magari le prime $5$ tessere sono troppo distanziate tra di loro e non è vero che far cadere la terza tessera fa cadere la quarta tessera. D’altro canto dalla quinta tessera in poi tutto funziona liscio come l’olio. Per questo motivo possiamo generalizzare il nostro principio facendo partire il nostro passo base da qualche $n_0$ che non sia necessariamente $1$ . Formalmente