Le raisonnement par récurrence est une technique de démonstration mathématique puissante, particulièrement adaptée pour prouver des propriétés sur les suites définies par une relation de récurrence. L’idée est analogue à un effet domino : si on peut faire tomber le premier domino, et si chaque domino en tombant entraîne le suivant, alors tous les dominos tomberont.
Soit $P(n)$ une propriété qui dépend d’un entier naturel $n$, et soit $n_0$ un entier naturel.
Pour démontrer que $P(n)$ est vraie pour tout entier $n \ge n_0$, on procède en deux étapes :
- Initialisation : On vérifie que la propriété est vraie pour le premier rang, c’est-à-dire que $P(n_0)$ est vraie.
- Hérédité : On suppose que la propriété $P(k)$ est vraie pour un certain entier $k \ge n_0$ (c’est l’hypothèse de récurrence), et on démontre que, sous cette hypothèse, la propriété est également vraie au rang suivant, c’est-à-dire que $P(k+1)$ est vraie.
Si ces deux étapes sont validées, on peut conclure que la propriété $P(n)$ est vraie pour tout entier $n \ge n_0$.
La Stratégie en 3 Étapes Appliquée aux Suites
- Étape 1 : Initialisation. On calcule le premier terme de la suite (par exemple $u_{n_0}$) et on vérifie qu’il satisfait la propriété $P(n_0)$.
- Étape 2 : Hérédité.
- On énonce clairement l’hypothèse de récurrence : « Supposons que $P(k)$ est vraie pour un certain entier $k \ge n_0$ ». Par exemple : « Supposons que $u_k < 2$".
- On utilise la définition de la suite (la relation $u_{k+1} = f(u_k)$) et l’hypothèse de récurrence pour démontrer que $P(k+1)$ est vraie. C’est le cœur de la démonstration.
- Étape 3 : Conclusion. On conclut en invoquant le principe de récurrence : « La propriété étant initialisée et héréditaire, elle est vraie pour tout entier $n \ge n_0$ ».
Exemple : Démontrer qu’une suite est majorée
Soit la suite $(u_n)$ définie par $u_0 = 1$ et, pour tout $n \in \mathbb{N}$, $u_{n+1} = \sqrt{3u_n + 4}$.
Montrons par récurrence que pour tout $n \in \mathbb{N}$, la suite est majorée par 4, c’est-à-dire $u_n < 4$.
Soit $P(n)$ la propriété : « $u_n < 4$".
Étape 1 (Initialisation) :
Pour $n=0$, on a $u_0 = 1$. Or, $1 < 4$. Donc, la propriété $P(0)$ est vraie.
Étape 2 (Hérédité) :
Supposons que la propriété $P(k)$ est vraie pour un certain entier $k \ge 0$. C’est notre hypothèse de récurrence :
$$u_k < 4$$
Montrons que $P(k+1)$ est vraie, c'est-à-dire que $u_{k+1} < 4$.
On part de l’hypothèse :
$u_k < 4$
On multiplie par 3 : $3u_k < 12$
On ajoute 4 : $3u_k + 4 < 16$
Comme la fonction racine carrée est strictement croissante sur $\mathbb{R}^+$, et que $3u_k+4$ est positif (on pourrait le prouver par une autre récurrence simple), on peut appliquer la racine :
$\sqrt{3u_k + 4} < \sqrt{16}$
Ce qui nous donne : $u_{k+1} < 4$.
Ainsi, l’hérédité est prouvée : si $P(k)$ est vraie, alors $P(k+1)$ est vraie.
Étape 3 (Conclusion) :
La propriété est initialisée au rang 0 et est héréditaire. Donc, par le principe de récurrence, on conclut que pour tout entier naturel $n$, $u_n < 4$.
La récurrence est un réflexe à avoir pour les suites définies par $u_{n+1}=f(u_n)$ lorsque l’on veut prouver :
- Qu’une suite est majorée, minorée ou bornée (comme dans l’exemple ci-dessus).
- La monotonie d’une suite, en étudiant le signe de $u_{n+1}-u_n$ si l’expression de $u_n$ est connue, ou en prouvant par récurrence que $u_{n+1} \ge u_n$ pour tout $n$.
- Une formule explicite pour $u_n$ en fonction de $n$. On vérifie que la formule est vraie pour $n_0$, puis on montre que si elle est vraie au rang $k$, elle l’est aussi au rang $k+1$.