Lien avec les preuves par récurrence

Si on veut montrer que tout élément de $\mbox{I\hspace{-.15em}N}$ vérifie une propriété, par exemple $\forall n \in \mbox{I\hspace{-.15em}N}$, $n(n+1)$ est pair, on va construire par induction l'ensemble $E \subset \mbox{I\hspace{-.15em}N}$ des $n \in \mbox{I\hspace{-.15em}N}$ tels que $n(n+1)$ est pair. Si les atomes de $\mbox{I\hspace{-.15em}N}$ et de $E$ sont les mêmes et que l'on parvient à construire $\mbox{I\hspace{-.15em}N}$ et $E$ avec les mêmes règles, alors $\mbox{I\hspace{-.15em}N}= E$. Nous avons deux étapes à effectuer pour le vérifier :

• Base la seul atome de $\mbox{I\hspace{-.15em}N}$ est $0$. Comme $0\times 1 = 0$ est pair, alors $0 \in E$.
• Induction La seule règle que nous avons à examiner est $s : x \mapsto x + 1$. Prenons un élément arbitraire de $E$ ($E$ n'est pas vide puisqu'il contient $0$), notons-le $n$. Montrons que $s(n) \in E$. On a $s(n) = n+1$, donc $s(n) \in E$ si $(n+1)(n+1)$ est pair. Or $(n+1)(n+2) = (n+1)n + (n+1)2$, comme $n \in E$, alors $n(n+1)$ pair. Par ailleurs $2(n+1)$ est évidemment pair. Comme la somme de deux nombres pairs est paire, alors $s(n) \in E$.

Nous venons de montrer que $\mbox{I\hspace{-.15em}N}$ peut être construit de la même façon que $E$, donc $\mbox{I\hspace{-.15em}N}\subset E$ (et par conséquent $E = \mbox{I\hspace{-.15em}N}$). Comme $E$ est l'ensemble des entiers $n$ tels que $n(n+1)$ est pair, alors pour tout élément $n$ de $\mbox{I\hspace{-.15em}N}$, $n(n+1)$ est pair. Ce que nous venons de faire est en fait une preuve par récurrence. La raisonnement par récurrence est un cas particulier du raisonnement par induction.