Définition
Le raisonnement par récurrence est une méthode de démonstration utilisée pour prouver qu'une propriété $P(n)$ est vraie pour tout entier naturel $n$ à partir d'un certain rang $n_0$. Il repose sur deux étapes fondamentales : l'initialisation et l'hérédité.
Méthode — Raisonnement par récurrence : principe et méthode
Étape 1 : Initialisation
On vérifie que la propriété $P(n)$ est vraie pour le premier terme, c'est-à-dire pour $n=n_0$. Cela consiste à calculer $P(n_0)$ et à montrer qu'elle est satisfaite.
Étape 2 : Hérédité (Hypothèse de récurrence)
On suppose que la propriété $P(k)$ est vraie pour un entier naturel $k \geq n_0$ fixé. Cette supposition est appelée l'hypothèse de récurrence. On écrit explicitement ce que signifie $P(k)$.
Étape 3 : Hérédité (Démonstration)
À partir de l'hypothèse de récurrence $P(k)$, on démontre que la propriété $P(k+1)$ est également vraie. Il s'agit de montrer que si $P(k)$ est vraie, alors $P(k+1)$ l'est aussi. C'est souvent l'étape la plus délicate et elle nécessite une manipulation algébrique ou une argumentation logique rigoureuse.
Étape 4 : Conclusion
Si les étapes d'initialisation et d'hérédité sont toutes deux vérifiées, alors on peut conclure, d'après le principe de récurrence, que la propriété $P(n)$ est vraie pour tout entier naturel $n \geq n_0$.
Exemple résolu
Soit la suite $(u_n)$ définie par $u_0 = 0$ et pour tout entier naturel $n$, $u_{n+1} = 2u_n + 1$. Démontrer par récurrence que pour tout entier naturel $n$, $u_n = 2^n - 1$.
D'une part, $u_0 = 0$.
D'autre part, $2^0 - 1 = 1 - 1 = 0$.
Donc $u_0 = 2^0 - 1$. La propriété est vraie pour $n=0$.
D'après la définition de la suite, $u_{k+1} = 2u_k + 1$.
En utilisant l'hypothèse de récurrence ($u_k = 2^k - 1$), on substitue $u_k$ :
$u_{k+1} = 2(2^k - 1) + 1$
$u_{k+1} = 2^{k+1} - 2 + 1$
$u_{k+1} = 2^{k+1} - 1$.
La propriété est donc vraie pour $k+1$.
Ainsi, pour tout entier naturel $n$, $u_n = 2^n - 1$.
⚠️ Piège fréquent au BAC — Oubli ou erreur dans les étapes
- Oublier l'initialisation ou la faire sur un rang incorrect ($n_0$ doit être le premier rang pour lequel la propriété est affirmée).
- Confondre l'hypothèse de récurrence ($P(k)$ est vraie) avec ce qu'il faut démontrer ($P(k+1)$ est vraie).
- Ne pas utiliser l'hypothèse de récurrence dans la démonstration de l'hérédité. Si l'hypothèse n'est pas utilisée, ce n'est pas une démonstration par récurrence.
- Faire des erreurs de calcul ou de manipulation algébrique lors de la démonstration de l'hérédité.
Exercice type BAC
On considère la suite $(u_n)$ définie par $u_0 = 2$ et pour tout entier naturel $n$, $u_{n+1} = rac{1}{2}u_n + 3$.
- Calculer $u_1$ et $u_2$.
- Démontrer par récurrence que pour tout entier naturel $n$, $u_n < 6$.
- Démontrer par récurrence que la suite $(u_n)$ est croissante.
Calcul de $u_1$ et $u_2$ :
$u_1 = rac{1}{2}u_0 + 3 = rac{1}{2}(2) + 3 = 1 + 3 = 4$.
$u_2 = rac{1}{2}u_1 + 3 = rac{1}{2}(4) + 3 = 2 + 3 = 5$.
Démonstration par récurrence que pour tout entier naturel $n$, $u_n < 6$ :
Initialisation : Pour $n=0$, $u_0 = 2$. On a bien $2 < 6$. La propriété est vraie pour $n=0$.
Hérédité : Supposons que pour un entier naturel $k \geq 0$ fixé, la propriété $u_k < 6$ est vraie (hypothèse de récurrence).
Montrons que $u_{k+1} < 6$.
On sait que $u_{k+1} = rac{1}{2}u_k + 3$.
D'après l'hypothèse de récurrence, $u_k < 6$.
Multiplions par $ rac{1}{2}$ (qui est positif) : $ rac{1}{2}u_k < rac{1}{2} × 6$, soit $ rac{1}{2}u_k < 3$.
Ajoutons 3 aux deux membres de l'inégalité : $ rac{1}{2}u_k + 3 < 3 + 3$, soit $u_{k+1} < 6$.
La propriété est donc vraie pour $k+1$.
Conclusion : Puisque la propriété est vraie pour $n=0$ et qu'elle est héréditaire, alors d'après le principe de récurrence, pour tout entier naturel $n$, $u_n < 6$.
Démonstration par récurrence que la suite $(u_n)$ est croissante :
On veut montrer que pour tout entier naturel $n$, $u_{n+1} \geq u_n$.
Initialisation : Pour $n=0$, on a $u_0 = 2$ et $u_1 = 4$. On a bien $u_1 \geq u_0$ ($4 \geq 2$). La propriété est vraie pour $n=0$.
Hérédité : Supposons que pour un entier naturel $k \geq 0$ fixé, la propriété $u_{k+1} \geq u_k$ est vraie (hypothèse de récurrence).
Montrons que $u_{k+2} \geq u_{k+1}$.
On sait que $u_{k+1} = rac{1}{2}u_k + 3$ et $u_{k+2} = rac{1}{2}u_{k+1} + 3$.
Considérons la différence $u_{k+2} - u_{k+1}$ :
$u_{k+2} - u_{k+1} = ( rac{1}{2}u_{k+1} + 3) - ( rac{1}{2}u_k + 3)$
$u_{k+2} - u_{k+1} = rac{1}{2}u_{k+1} - rac{1}{2}u_k$
$u_{k+2} - u_{k+1} = rac{1}{2}(u_{k+1} - u_k)$.
D'après l'hypothèse de récurrence, $u_{k+1} \geq u_k$, ce qui signifie que $u_{k+1} - u_k \geq 0$.
Donc, $ rac{1}{2}(u_{k+1} - u_k) \geq 0$.
Par conséquent, $u_{k+2} - u_{k+1} \geq 0$, ce qui implique $u_{k+2} \geq u_{k+1}$.
La propriété est donc vraie pour $k+1$.
Conclusion : Puisque la propriété est vraie pour $n=0$ et qu'elle est héréditaire, alors d'après le principe de récurrence, la suite $(u_n)$ est croissante pour tout entier naturel $n$.
Questions fréquentes
Quand faut-il utiliser le raisonnement par récurrence ?
Peut-on faire une récurrence sur des nombres réels ?
Que se passe-t-il si l'initialisation échoue ?
Est-il toujours nécessaire d'écrire 'Hypothèse de récurrence' explicitement ?
Pour aller plus loin
Vous bloquez sur ce chapitre ?
Adil accompagne les lycéens en Terminale Spécialité, en ligne ou à domicile dans le Val d'Oise. Résultats en 1 séance.