Il principio di induzione

Quando vogliamo dimostrare che una proprietà $P(n)$ vale per tutti i numeri naturali $n\ge n_0$ non possiamo verificarla uno a uno: i naturali sono infiniti. Il principio di induzione fornisce uno schema in due passi che “chiude” la dimostrazione in un colpo solo.

Teorema — Principio di induzione matematica

Sia $P(n)$ una proposizione definita per ogni $n\in\mathbb{N}$, $n\ge n_0$. Se:

• (base) $P(n_0)$ è vera;
• (passo induttivo) per ogni $k\ge n_0$, $P(k)\Rightarrow P(k+1)$,

allora $P(n)$ è vera per ogni $n\ge n_0$.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Numeri naturali · Principio di induzione
Metodi: Induzione
Competenze: Dimostrare