Cos’è il principio di induzione
Il principio di induzione è un metodo di dimostrazione e può essere usato per mostrare la veridicità di una proprietà matematica \({{P}_{n}}\) valida per ogni \(n\ge {{n}_{0}}\) con \(n\in \mathbb{N}\).
Ad esempio, proprietà di questo tipo possono essere \({{P}_{n}}:\,\,{{2}^{n-1}}\le n!\,\,,\,\,\,n\ge 1\) oppure \({{P}_{n}}:\,\,\,\,\sum\limits_{k=1}^{n}{{{k}^{2}}}=\)\(\frac{n\left( n+1 \right)\left( 2n+1 \right)}{6}\,\,\,,\,\,\,\,n\ge\ 1\) . Tra un pò andremo a dimostrarle.
Ma prima vediamo lo schema per il principio di induzione.
Funziona un po’ come il gioco del domino e cioè per far vedere che le pedine cadono tutte, bisogna far vedere che ci sono le condizioni per far cadere la prima e che se cade una generica pedina n-esima allora cadrà anche quella successiva cioè la (n+1)-esima.
Nel caso di una proprietà matematica bisogna dimostrare che:
(i) \({{P}_{{{n}_{0}}}}\) è vera.
(ii) Passo induttivo. Vale l’implicazione \({{P}_{n}}\Rightarrow {{P}_{n+1}}\) , che si legge: Se è vero \({{P}_{n}}\) (ipotesi) allora è vero \({{P}_{n+1}}\) (tesi)
Ora vediamo subito alcuni esempi per chiarirci meglio le idee.
Esempio 1
Partiamo dal primo esempio \({{P}_{n}}:\,\,{{2}^{n-1}}\le n!\,\,,\,\,\,n\ge 1\)
Dimostriamo il punto (i) \({{P}_{1}}\) è vera. Verifichiamo sostituendo n=1 nella proprietà \({{2}^{1-1}}\le 1!\,\,\,\,\Rightarrow \,\,1\le 1\) ed è vero, quindi il primo punto è verificato.
Dimostriamo ora il punto (ii) \({{P}_{n}}\Rightarrow {{P}_{n+1}}\)
Supponiamo vera\({{P}_{n}}:\,\,{{2}^{n-1}}\le n!\,\,\)A questo punto moltiplichiamo entrambi i membri per due\({{2}^{n}}\le 2\,n!\) Osserviamo che \(2\le n+1\,,\,\,\forall n\ge 1\) e quindi \(2\cdot n!\le \left( n+1 \right)n!\) D’altronde \(\left( n+1 \right)n!=\left( n+1 \right)!\) e quindi si può scrivere \({{2}^{n}}\le \left( n+1 \right)!\) che corrisponde a\({{P}_{n+1}}\). In questo modo abbiamo dimostrato che a partire da \({{P}_{n}}\) si arriva a \({{P}_{n+1}}\) tramite regolari passaggi matematici.
Esempio 2
Vogliamo dimostrare che vale \({{P}_{n}}:\,\,\,\,\sum\limits_{k=1}^{n}{{{k}^{2}}}=\frac{n\left( n+1 \right)\left( 2n+1 \right)}{6}\,\,\,,\,\,\,\,n\ge 1\)
Dimostriamo il punto (i) \({{P}_{1}}\) è vera. Verifichiamo sostituendo n=1 nella proprietà \({{1}^{2}}=\frac{1\left( 1+1 \right)\left( 2+1 \right)}{6}\,\) ed è vero, quindi il primo punto è verificato.
Dimostriamo ora il punto (ii) \({{P}_{n}}\Rightarrow {{P}_{n+1}}\)
Supponiamo vera \({{P}_{n}}\).
Allora anche \({{P}_{n+1}}:\,\,\,\,\sum\limits_{k=1}^{n+1}{{{k}^{2}}}=\frac{\left( n+1 \right)\left( n+2 \right)\left( 2\left( n+1 \right)+1 \right)}{6}\,\,\,\)dovrà essere vera. Scriviamo meglio: \(\,\sum\limits_{k=1}^{n+1}{{{k}^{2}}}=\frac{\left( n+1 \right)\left( n+2 \right)\left( 2n+3 \right)}{6}\,\,\,\)
Posso isolare l’(n+1)-esimo termine della sommatoria:\(\,\sum\limits_{k=1}^{n+1}{{{k}^{2}}}=\,\sum\limits_{k=1}^{n}{{{k}^{2}}}+{{\left( n+1 \right)}^{2}}\,\,\)e poiché vale \({{P}_{n}}\) posso scrivere \(\,\sum\limits_{k=1}^{n+1}{{{k}^{2}}}=\frac{n\left( n+1 \right)\left( 2n+1 \right)}{6}\,+{{\left( n+1 \right)}^{2}}\,\,\) \(=\frac{n\left( n+1 \right)\left( 2n+1 \right)+6{{\left( n+1 \right)}^{2}}}{6}\,\) \(=\left( n+1 \right)\frac{n\left( 2n+1 \right)+6n+6}{6}=\) \(\left( n+1 \right)\frac{2{{n}^{2}}+7n+6}{6}\) \(=\left( n+1 \right)\frac{\left( n+2 \right)\left( 2n+3 \right)}{6}\) .
Abbiamo quindi dimostrato che aggiungendo un termine alla sommatoria definita da \({{P}_{n}}\) si arriva a \({{P}_{n+1}}\) attraverso regolari passaggi di matematica.
