Il principio di induzione consente di verificare sin da subito se, nel campo dei numeri naturali, una proprietà è vera o falsa per ogni n numero naturale.
Un esempio che mi piace sempre portare per farla capire è la somma di Gauss: noi sappiamo che la somma dei numeri da 0 fino a n vale \sum_{i=0}^{n}x=\frac{n(n+1)}{2}
Col principio di induzione cosa facciamo? Semplicemente verifichiamo se questa formula è verificata davvero per tutti gli n numeri naturali. Cioè partiamo da una formula che supponiamo vera (in questo la formula di Gauss), verifichiamo che vale almeno in un caso (si può scegliere sia lo 0 che 1) e poi si deve tentare di verificare, assunto vero per n, che questa formula continui a valere anche per n+1, così abbiamo assicurato la sua valenza per tutti gli n numeri naturali.
Quindi, il primo passo è verificare se c'è la base induttiva: nel nostro caso partiamo da 0 e vediamo che:
P(n=0)=\sum_{i=0}^{0}x=\frac{0\cdot 1}{2}=0 e ci troviamo. La base induttiva ce l'abbiamo.
Ora verifichiamo se la formula vale anche per n+1, supposto vera per n come qui:
P(n)=\sum_{i=0}^{n}x=0+1+2+3+...+n=\frac{n\cdot (n+1)}{2} valga in realtà anche per
P(n+1)=\sum_{i=0}^{n+1}x=0+1+2+3+...+(n+1)=\frac{(n+1)\cdot [(n+1)+1]}{2}Per verificare ciò, basta fare una considerazione algebrica davvero rapida:
P(n+1)=0+1+2+3+...+n+(n+1)=P(n)+(n+1)=\\ \frac{n(n+1)}{2}+(n+1)= \frac{n(n+1)+2(n+1)}{2}=\\ \frac{(n+1)(n+2)}{2}= \frac{(n+1)[(n+1)+1]}{2}e abbiamo finito: se proviamo a sostituire (n+1) con n nell'espressione ci troviamo proprio identicamente con la formula che abbiamo supposto vera a priori.
Per il principio di induzione, possiamo affermare che la formula di Gauss è vera.
Se hai altri dubbi o domande, fammele sapere sempre qui sotto.
