Démonstration par récurrence : méthode et exemple

Le raisonnement par récurrence (ou induction) permet de démontrer qu'une propriété $P(n)$ est vraie pour tout entier $n \ge n_0$. C'est l'outil de base des démonstrations sur les entiers naturels.

Principe

Pour démontrer « $P(n)$ vraie pour tout $n \ge n_0$ », il suffit de prouver deux choses :

• Initialisation : $P(n_0)$ est vraie.
• Hérédité : pour tout $n \ge n_0$, si $P(n)$ est vraie, alors $P(n+1)$ l'est aussi.

Structure d'une démonstration

Une preuve par récurrence s'écrit toujours selon le même plan : énoncer $P(n)$, faire l'initialisation (souvent simple), supposer $P(n)$ vraie (« hypothèse de récurrence »), démontrer $P(n+1)$, conclure.

Erreur classique : oublier l'initialisation, ou utiliser une hypothèse plus forte que $P(n)$ sans le justifier.

Exemple : somme des n premiers entiers

Démontrons que pour tout $n \ge 1$ : $\sum_{k=1}^n k = \frac{n(n+1)}{2}$.

Initialisation (n=1) : $\sum_{k=1}^1 k = 1$ et $\frac{1 \cdot 2}{2} = 1$. ✓

Hérédité : supposons la propriété vraie pour un certain $n$. Alors : $$\sum_{k=1}^{n+1} k = \sum_{k=1}^n k + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\cdot\frac{n+2}{2} = \frac{(n+1)(n+2)}{2}$$

C'est exactement $P(n+1)$. ∎

Variantes utiles

• Récurrence forte : on suppose $P(k)$ vraie pour tous les $k \le n$, pas seulement $P(n)$. Utile quand $P(n+1)$ fait appel à plusieurs rangs précédents (suites définies par récurrence à plusieurs termes).
• Récurrence double : deux cas d'initialisation $P(n_0)$ et $P(n_0+1)$, puis hérédité $P(n), P(n+1) \Rightarrow P(n+2)$.
• Récurrence descendante : rare, utilisée dans certains contextes (inégalités de Jensen, par exemple).

Le principe mathématique sous-jacent

Pourquoi la récurrence fonctionne-t-elle ? Elle repose sur l'axiome du bon ordre de $\mathbb{N}$ : toute partie non vide de $\mathbb{N}$ admet un plus petit élément.

Si l'ensemble $\{n \in \mathbb{N} \mid P(n) \text{ fausse}\}$ était non vide, il admettrait un plus petit élément $n_1 > n_0$. Alors $P(n_1 - 1)$ serait vraie (car $n_1$ est le plus petit contre-exemple), mais par hérédité $P(n_1)$ serait aussi vraie — contradiction. Donc l'ensemble des contre-exemples est vide : $P(n)$ est vraie pour tout $n \ge n_0$.

Pièges classiques à éviter

• Oublier l'initialisation — l'hérédité seule ne prouve rien. Exemple fameux : on peut « démontrer » que tous les chevaux ont la même couleur par hérédité, mais l'initialisation pour 1 cheval est triviale et l'hérédité de $n$ à $n+1$ est vicieuse (elle suppose implicitement $n \ge 2$).
• Confondre ce qu'on suppose et ce qu'on veut démontrer — l'hypothèse de récurrence, c'est $P(n)$, pas $P(n+1)$.
• Utiliser des $P(k)$ pour $k < n$ alors qu'on a seulement supposé $P(n)$ — dans ce cas, utiliser la récurrence forte.
• Manipuler une inégalité fausse pour la rendre vraie — chaque étape de l'hérédité doit être une implication rigoureuse.

Exemple de récurrence forte

Démontrons que tout entier $n \ge 2$ est produit de nombres premiers.

Initialisation ($n=2$) : 2 est premier, c'est son propre produit. ✓

Hérédité forte : supposons que tout $k$ avec $2 \le k \le n$ est produit de premiers. Montrons-le pour $n+1$. Si $n+1$ est premier, c'est gagné. Sinon $n+1 = a \cdot b$ avec $2 \le a, b \le n$. Par hypothèse de récurrence forte, $a$ et $b$ sont produits de premiers, donc $n+1 = a \cdot b$ aussi.

La récurrence forte est ici indispensable : on utilise la propriété pour $a$ et $b$ qui sont différents de $n$.

Une question ou une suggestion ? Écrivez-nous.