Exemple

Montrons par récurrence sur $n$ que ``Quel que soit $n \geq 0$, $n^2 - n$ est pair'' :

• initialisation : , $0^2 - 0$ est pair, c'est évident.
• hérédité : , supposons que $n^2 - n$ est pair, vérifions si $(n+1)^2 - (n+1)$ est pair lui aussi. Calculons
  
  $$(n+1)^2 - (n+1) = n^2 + 2n + 1 - n - 1 = (n^2 - n) + 2n$$
  
  
  Comme $(n^2 - n)$ et $2n$ sont tous deux pairs, et que la somme de deux nombres pairs est paire, alors $(n+1)^2 - (n+1)$ est pair.

Demandons-nous si $2^2 - 2$ est pair, on sait d'après l'initialisation que $0^2 - 0$ est pair. Posons $n = 0$, comme la propriété est vérifiée au rang $n$, elle est, d'après l'hérédité, nécessairement vérifiée au rang $n+1$, donc $1^2 - 1$ est pair. Posons $n = 1$, comme $1^2 - 1$ est pair, la propriété est vérifiée au rang $n$, elle est, d'après l'hérédité, nécessairement vérifiée au rang $n+1$, donc $2^2 - 2$ est pair. On peut généraliser ce raisonnement à n'importe quelle valeur de $n$.