Facciamo un classico esempio di dimostrazione per induzione.
Dimostriamo che la somma dei primi $n$ numeri dispari e' esattamente pari a $n^2$:
$$
\sum_{k=0}^{n-1}\left(2k+1\right) = n^2
$$
Primo passo: dimostriamo che e' vera per $n=1$:
$$
\sum_{k=0}^{0}\left(2k+1\right) = 1^2
$$
cioe':
$$
1 = 1
$$
con eccesso di zelo, vediamo facilmente che e' vera anche per $n=2$:
$$
\sum_{k=0}^{1}\left(2k+1\right) = 2^2
$$
cioe':
$$
1 +3 = 4
$$
E adesso passiamo alla vera dimostrazione per induzione: assumiamola vera per un certo $n$ e dimostriamo che, se e' vera per quel $n$,allora e' vera anche per $n+1$, cioe' assumiamo che se vale:
$$
\sum_{k=0}^{n-1}\left(2k+1\right) = n^2
$$
Allora e' vero che:
$$
\sum_{k=0}^{n}\left(2k+1\right) = \left(n+1 \right)^2
$$
procediamo:
$$
\sum_{k=0}^{n}\left(2k+1\right) = \sum_{k=0}^{n-1}\left(2k+1\right) + 2n +1 = n^2+2n+1 = \left(n+1 \right)^2
$$
QED
