Induzione matematica — principio, passaggi ed esempi

L’induzione matematica è un metodo di dimostrazione usato per mostrare che un’affermazione è vera per ogni intero a partire da un certo valore iniziale. Per dimostrare una proprietà per tutti gli $n \ge n_0$, si mostra che il primo caso è vero e poi che la verità per un intero implica la verità per l’intero successivo.

Se entrambe le parti sono corrette, l’affermazione vale per ogni intero nell’intervallo indicato. Questa è l’idea fondamentale.

Come funziona l’induzione matematica

Scrivi l’affermazione come $P(n)$. Allora l’induzione ha questa struttura:

1. Dimostra il caso base: mostra che $P(n_0)$ è vera.
2. Dimostra il passo induttivo: mostra che, se $P(k)$ è vera per un intero arbitrario $k \ge n_0$, allora anche $P(k+1)$ è vera.

Una volta fatti questi due passaggi, puoi concludere che $P(n)$ è vera per ogni intero $n \ge n_0$.

La logica è sequenziale. Il caso base avvia la catena, e il passo induttivo fa avanzare la catena di un intero alla volta.

Perché il caso base e il passo induttivo sono entrambi importanti

Il caso base ti fornisce la prima affermazione vera. Il passo induttivo dice che la verità passa da un intero al successivo.

Quindi, se $P(n_0)$ è vera, allora è vera anche $P(n_0 + 1)$. Poi è vera $P(n_0 + 2)$, e così via. L’induzione non salta il punto di partenza e non salta il collegamento tra un caso e il successivo.

Esempio svolto: dimostrare una formula di somma per induzione

Un esempio classico è la formula

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

per tutti gli interi $n \ge 1$.

Sia

$$P(n): 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$$

Caso base

Prendi $n = 1$. Il lato sinistro è $1$, e il lato destro è

$$\frac{1(1+1)}{2} = 1$$

Quindi $P(1)$ è vera.

Passo induttivo

Supponi che $P(k)$ sia vera per un intero arbitrario $k \ge 1$. Questo significa che

$$1 + 2 + 3 + \cdots + k = \frac{k(k+1)}{2}$$

Ora dimostra $P(k+1)$. Parti dal lato sinistro per $k+1$:

$$1 + 2 + 3 + \cdots + k + (k+1)$$

Usando l’ipotesi induttiva,

$$\frac{k(k+1)}{2} + (k+1)$$

Raccogliendo $(k+1)$:

$$(k+1)\left(\frac{k}{2} + 1\right)$$

Poi semplifica:

$$(k+1)\left(\frac{k+2}{2}\right) = \frac{(k+1)(k+2)}{2}$$

Questa è esattamente la formula con $n = k+1$. Quindi $P(k+1)$ è vera.

Poiché sia il caso base sia il passo induttivo sono stati dimostrati, la formula vale per tutti gli interi $n \ge 1$.

Quando usare l’induzione matematica

L’induzione è utile quando un’affermazione dipende da un parametro intero e ogni caso si collega naturalmente a uno precedente. Questo accade spesso con somme, affermazioni di divisibilità, disuguaglianze, relazioni di ricorrenza e dimostrazioni di algoritmi.

Per prima cosa, individua il valore iniziale corretto. Alcune proprietà iniziano da $n = 0$, altre da $n = 1$, e altre ancora hanno senso solo per interi più grandi.

Poi controlla qual è il caso valido successivo. Il passaggio usuale è da $k$ a $k+1$, ma se l’affermazione riguarda solo interi pari, un passaggio da $k$ a $k+2$ può essere la versione giusta.

Errori comuni nelle dimostrazioni per induzione

Dimostrare solo il caso base

Il caso base verifica solo il primo valore. Da solo, non dimostra l’affermazione per gli interi successivi.

Usare il valore iniziale sbagliato

Se l’affermazione deve valere per tutti gli $n \ge 2$, dimostrare solo $P(1)$ non aiuta. Il caso base deve corrispondere all’intervallo reale dell’affermazione.

Trattare con poca attenzione l’ipotesi induttiva

Nel passo induttivo, assumi $P(k)$ per un solo intero arbitrario $k$ nell’intervallo valido. Non stai assumendo che l’intero teorema sia già dimostrato.

Dimostrare il caso successivo sbagliato

Se il tuo teorema richiede un passaggio $k \to k+1$, dimostrare un passaggio diverso non conclude l’argomento, a meno che tu non spieghi perché quel passaggio diverso è sufficiente.

Un’estensione utile: l’induzione forte

A volte per dimostrare $P(k+1)$ serve più di $P(k)$. In questa situazione, l’induzione forte ti permette di assumere tutti i casi precedenti fino a $k$ e poi dimostrare quello successivo.

L’idea è strettamente collegata, ma l’ipotesi è più forte. È utile, per esempio, quando una dimostrazione dipende dal fatto di scomporre un numero in parti più piccole.

Prova la tua versione

Prendi l’affermazione

$$1 + 3 + 5 + \cdots + (2n - 1) = n^2$$

e dimostrala per tutti gli interi $n \ge 1$ usando la stessa struttura: prima il caso base, poi il passaggio da $k$ a $k+1$. Se riesci a scrivere bene questa dimostrazione, di solito il metodo diventa chiaro.