Consideriamo questa scrittura:
La formula mostrata viene ipotizzata vera, senza dimostrazione.
La utilizzeremo per effettuare la dimostrazione.
Iniziamo a scriverla diversamente:
Possiamo ora dimostrare la correttezza della legge a fianco riportata, utilizzando il principio di induzione.
- Lo verifichiamo per n=0: la sommatoria si riduce al primo termine e quindi 20=1 a cui corrisponde 2¹-1=2-1, quindi 1=1 come richiesto;
- Lo ipotizziamo valido per n; ossia affermiamo che supponiamo corretto
- lo dimostriamo vero per n+1.
Ora per effettuare questa dimostrazione sfruttiamo il secondo punto e calcoliamo 1+4+8+16+...+2n+ 2n+1= (1+4+8+16+...+2n)+2n+1= 2n+1 -1 + 2n+1 = 2 x 2n+1 -1 . Questo può essere scritto anche come 2n+2 -1.
Questa è esattamente la formula che dovevamo ricavare, tenendo presente che per l'ultimo termine pari a 2n+1 impone che la somma di tutti i termini sia 2 elevato a n+1+1 ossia a n+2, il tutto -1.
Il principio d'induzione è una tecnica potente.
Se dimostriamo che la formula è corretta per n=1 e sappiamo che vale sempre per il successivo. Pertanto se vale per n=1 vale anche per n=2 e per n=3 ossia vale per ogni n.
Con questo procedimento possiamo dimostrare la correttezza di formule nuove, regole non derivate da altre note.
A differenza di ciò che dimostriamo utilizzando il metodo deduttivo, qui è possibile ricavare leggi nuove, non implicite in ciò che già sappiamo.
Cosa devo avere per poter iniziare una dimostrazione utilizzando il principio di induzione?
Un elenco di numeri legati tra di loro.
Il primo elemento e la legge da ricavare applicabile sicuramente all'elemento assegnato.
Alcuni elementi e una legge generale dipendente da n e corretta per il primo elemento.