Le molteplici volti del ragionamento per induzione

-

Si consideri una proprietà $\mathcal{P}(n)$ enunciata per un certo numero naturale n. Per dimostrare che questa proprietà è vera per ogni numero naturale, si può procedere in due fasi.

La prima, l’inizializzazione, consiste nel dimostrare che $\mathcal{P}(0)$ è vera.

La seconda, la dimostrazione del carattere ereditario della proprietà, consiste nel mostrare che, se $\mathcal{P}(n)$ è vera per un qualunque numero naturale n, allora anche $\mathcal{P}(n+1)$ è vera. Spesso questo principio viene illustrato con una fila di tessere di domino che cadono una dopo l’altra dopo aver spinto la prima.

Esistono diverse varianti di questo principio, che restano comunque equivalenti a questa «induzione semplice». Naturalmente si può inizializzare il ragionamento a partire da un numero intero non nullo n₀ e si concluderà che $\mathcal{P}(n)$ è vera per ogni intero n maggiore o uguale a n₀. Si può anche ricorrere a una «induzione doppia»; in questo caso si dimostra che $\mathcal{P}(0)$ e $\mathcal{P}(1)$ sono vere, poi che, se $\mathcal{P}(n-1)$ e $\mathcal{P}(n)$ sono vere, allora anche $\mathcal{P}(n+1)$ lo è. Si può persino arrivare a una «induzione forte», in cui, per dimostrare che $\mathcal{P}(n+1)$ è vera, si suppone che la proprietà sia vera per tutti gli indici inferiori.