Principe de récurrence

Nous allons voir maintenant que la structure de l'ensemble $\mathbb{N}$ permet une nouvelle technique de démonstration: la démonstration par récurrence.

Idée générale du principe de récurrence

Supposons que nous devions démontrer une formule qui dépend uniquement d'un nombre naturel $n$, c'est à dire une propriété vraie pour tout $n\in \mathbb{N}$. Si cette propriété est $P$, on a que $P(n)$ est vrai quel que soit $n$. Le problème est de savoir comment démontrer que $P(n)$ est toujours vrai.

En effet, on peut écrire une démonstration pour démontrer que $P(0)$ est vrai. Puis faire la même chose pour $P(1)$, puis pour $P(2)$, ... mais on n'aura jamais fini la démonstration. Face à ce problème, on peut tenter de prouver $P(n)$ sans faire d'hypothèse sur $n$ c'est à dire que l'on démontre directement $P(n)$ mais ce n'est pas toujours possible ni toujours facile.

Il est cependant parfois possible de démontrer que si pour un certain $n$ $P(n)$ est vrai, alors $P(s(n))$ est vrai aussi. L'idée est donc de montrer d'abord que $P(0)$ est vrai. On suppose alors que $P(n)$ est vrai pour un certain $n$ ce que l'on appelle l'hypothèse de récurrence. Ensuite on démontre que $P(s(n))$ est vrai avec cette hypothèse.

Cette démarche est suffisante pour prouver $P(n)$ pour tout $n\in \mathbb{N}$. En effet, on sait que $P(0)$ est vrai (car on le démontre au préalable). Puisqu'on montre ensuite que si $P(n)$ est vrai, alors $P(s(n))$ est vrai aussi, cela veut dire que $P(1)$ est vrai car $P(0)$ est vrai. De la même manière, cela prouve que $P(2)$ est vrai puisque $P(1)$ est vrai, et donc $P(3)$ et ainsi de suite. On a donc démontré $P(n)$ pour tout $n$.

Écriture formelle du principe

Dans une démonstration par récurrence on démontre $P(0)$ et on démontre $\forall n\in \mathbb{N},P(n)\Rightarrow P(s(n))$. Remarquez qu'on devrait écrire formellement: $\forall n,(n\in \mathbb{N}\wedge P(n)\Rightarrow P(s(n)))$ mais on ne le fait pas pour rendre l'écriture de la formule plus facile à lire. Désormais on va accepter ce léger abus de notation.

Le principe de récurrence nous dit donc que si ces deux choses sont prouvées, alors on a montré $\forall n\in \mathbb{N},P(n)$. On a donc:

Démonstration

Il reste à démontrer cette formule. On suppose donc que $P(0)$ et $\forall n\in \mathbb{N},P(n)\Rightarrow P(s(n))$ sont vrais et on démontre $\forall n\in \mathbb{N},P(n)$. On va le faire par l'absurde. Supposons qu'il existe $n\in \mathbb{N}$ tel que $P(n)$ soit faux. On considère le plus petit $n$ tel que $P(n)$ soit faux, et on le note $m$. $m\ne 0$ car on sait que $P(0)$ est vrai. $m$ est donc le successeur d'un entier $p$. $p$ est donc plus petit que $m$ et donc $P(p)$ est vrai. On a donc par hypothèse que $P(s(p))=P(m)$ est vrai et on a une contradiction.