Le molteplici volti del ragionamento per induzione

-

Si consideri una proprietà $\mathcal{P}(n)\backslash 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)\backslash mathcal\{P\}(0)$ è vera.

La seconda, la dimostrazione del carattere ereditario della proprietà, consiste nel mostrare che, se $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ è vera per un qualunque numero naturale n, allora anche $\mathcal{P}(n+1)\backslash 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)\backslash 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)\backslash mathcal\{P\}(0)$ e $\mathcal{P}(1)\backslash mathcal\{P\}(1)$ sono vere, poi che, se $\mathcal{P}(n-1)\backslash mathcal\{P\}(n\; -\; 1)$ e $\mathcal{P}(n)\backslash mathcal\{P\}(n)$ sono vere, allora anche $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ lo è. Si può persino arrivare a una «induzione forte», in cui, per dimostrare che $\mathcal{P}(n+1)\backslash mathcal\{P\}(n\; +\; 1)$ è vera, si suppone che la proprietà sia vera per tutti gli indici inferiori.