Il principio di induzione

Il principio d'induzione è un enunciato sui numeri naturali che risulta molto utile nelle dimostrazioni in cui si vuole provare che una certa proprietà è valida per tutti i numeri naturali.


L'idea su cui si basa è quella dell'effetto domino: affinché le tessere da domino disposte lungo una fila cadano tutte, sono sufficienti due condizioni:

  • che cada la prima tessera;

  • che ogni tessera sia posizionata in modo tale che, cadendo, provochi la caduta della tessera successiva.

Il principio d'induzione estende quest'idea al caso in cui la fila sia composta da infinite tessere e l'utilizza nelle dimostrazioni che riguardano i numeri naturali.

Principio d'induzione


Data una proprietà P che riguarda i numeri naturali,

se sono verificate le seguenti condizioni:

1. P vale per un numero iniziale (può essere 0 o 1 o…);

2. ogni volta che P vale per un numero naturale m, P vale anche per il numero naturale successivo, m+1,

allora, la proprietà P vale per tutti i numeri naturali.

Il punto 1 è chiamato base dell'induzione, il punto 2 è chiamato passo induttivo.

Praticamente, funziona così:

  1. si dimostra in modo diretto (sostituendo) la base dell'induzione, cioè che la proprietà vale per un numero iniziale;

  2. si dimostra che la proprietà vale per m+1, "innestando" la proprietà relativa ad m nella dimostrazione, per provare che il fatto che la proprietà valga per m basta a garantire che quella proprietà valga anche per m+1 (passo induttivo).

Esempio

In altre parole, per dimostrare che la proprietà vale per n+1, si fa in modo di poter applicare la proprietà per n (che si suppone valida); cioè si cerca il modo di inserire la formula P(n) all'interno della formula P(n+1). In questo modo, dalla validità di P(n) si deduce la validità di P(n+1).

Il primo utilizzo del principio d'induzione in una dimostrazione risale al 1575, da parte di Francesco Maurolico. Nel XVII secolo Pierre de Fermat ne ha raffinato l'utilizzo, formulandolo come principio della discesa infinita.
Il principio d'induzione si trova anche nei lavori di Blaise Pascal (1653).

Sembra che l'espressione "induzione matematica" sia stata coniata dal logico e matematico A. De Morgan nei primi del XIX secolo.
La sua formulazione completa, usata ancora oggi, è essenzialmente quella data da Giuseppe Peano negli "Arithmetices Principia", pubblicati nel 1889. Il principio d'induzione deriva direttamente dal quinto assioma di Peano, ed è ad esso equivalente: cioè, assumendolo come assioma, da esso deriva il quinto assioma di Peano.