Raisonnement par récurrence

Démontrer qu'une propriété est vraie pour tout entier n : initialisation, hérédité, conclusion.

1 L'idée

Le raisonnement par récurrence est une méthode de démonstration permettant de prouver qu'une propriété $P(n)$ est vraie pour tout entier $n$ à partir d'un certain rang $n_0 \in \mathbb{N}$.

L'analogie classique est celle des dominos : si le premier tombe (initialisation) et si chaque domino fait tomber le suivant (hérédité), alors tous tombent. La récurrence formalise exactement ce raisonnement.

2 Le principe logique

Initialisation

$\text{Vérifier } P(n_0)$

Hérédité

$\forall n \geq n_0,\quad P(n) \Rightarrow P(n+1)$

Conclusion

$\Rightarrow\;\forall n \geq n_0,\quad P(n) \text{ est vraie}$

Rédaction en trois étapes

1. Initialisation : énoncer $P(n_0)$ et la vérifier par un calcul explicite.
2. Hérédité : fixer un entier $n \geq n_0$ quelconque ; énoncer clairement l'hypothèse de récurrence « on suppose $P(n)$ vraie » ; puis démontrer $P(n+1)$ en utilisant cette hypothèse.
3. Conclusion : rappeler les deux étapes et écrire : « Par le principe de récurrence, $P(n)$ est vraie pour tout $n \geq n_0$. »

4 Exemple complet — Somme des entiers

Propriété

Montrer que pour tout $n \geq 1$ : $\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$.

Initialisation (n = 1)

$\displaystyle\sum_{k=1}^{1} k = 1$ et $\dfrac{1 \times 2}{2} = 1$. Les deux membres sont égaux : $P(1)$ est vraie.

Hérédité

Soit $n \geq 1$. On suppose $\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$ (hypothèse de récurrence).

$\displaystyle\sum_{k=1}^{n+1} k = \displaystyle\sum_{k=1}^{n} k + (n+1) = \dfrac{n(n+1)}{2} + (n+1) = \dfrac{n(n+1)+2(n+1)}{2} = \dfrac{(n+1)(n+2)}{2}$.

C'est bien la formule au rang $n+1$ : $P(n+1)$ est vraie.

Conclusion

$P(1)$ est vraie et $P(n) \Rightarrow P(n+1)$ pour tout $n \geq 1$ ; donc, par récurrence, $\displaystyle\sum_{k=1}^{n} k = \dfrac{n(n+1)}{2}$ pour tout $n \geq 1$.

Erreurs fréquentes

Oublier l'initialisation : une récurrence sans initialisation ne prouve rien.
Ne pas énoncer explicitement l'hypothèse de récurrence avant de l'utiliser dans l'hérédité.
Ne pas utiliser l'hypothèse de récurrence dans le calcul : c'est l'erreur la plus grave.
Raisonnement circulaire : utiliser ce qu'on veut démontrer pour le démontrer.