Raisonnement par récurrence : méthode et exemples corrigés
Le raisonnement par récurrence est l'outil qui permet de démontrer qu'une propriété est vraie pour tous les entiers, sans les vérifier un par un — ce qui serait impossible puisqu'il y en a une infinité.
ViragePrépa
Le raisonnement par récurrence est l'outil qui permet de démontrer qu'une propriété est vraie pour tous les entiers, sans les vérifier un par un — ce qui serait impossible puisqu'il y en a une infinité. L'idée est celle d'une rangée de dominos : si l'on fait tomber le premier, et si chaque domino qui tombe entraîne la chute du suivant, alors toute la rangée tombe. La récurrence formalise exactement cette intuition et en fait une méthode de démonstration rigoureuse, incontournable de la terminale jusqu'aux concours.
Sa force est aussi sa difficulté : la démonstration par récurrence repose sur une structure très précise, en trois temps, dont chaque étape doit être rédigée avec soin. Un oubli — l'initialisation négligée, une hérédité mal posée — et toute la preuve s'effondre. Ce cours détaille le principe, la rédaction type à reproduire, les variantes (récurrence simple, double, forte) et de nombreux exemples corrigés, pour faire de la récurrence un réflexe sûr.
Le principe du raisonnement par récurrence
Soit P(n) une propriété qui dépend d'un entier naturel n. On veut montrer que P(n) est vraie pour tout n supérieur ou égal à un certain rang n₀. Le principe de récurrence affirme qu'il suffit pour cela de vérifier deux choses : d'une part que la propriété est vraie au départ, d'autre part qu'elle se « transmet » d'un entier au suivant.
Si P(n₀) est vraie, et si pour tout n ≥ n₀, P(n) ⇒ P(n+1), alors P(n) est vraie pour tout n ≥ n₀
L'image des dominos éclaire parfaitement ce mécanisme. L'initialisation, c'est faire tomber le premier domino : on s'assure qu'il tombe bien. L'hérédité, c'est garantir que chaque domino en tombant renverse le suivant. Si ces deux conditions sont réunies, la chute se propage de proche en proche à toute la rangée, aussi longue soit-elle. La conclusion ne fait qu'énoncer ce résultat : tous les dominos tombent, la propriété est vraie pour tout n.
Les trois étapes à ne jamais oublier
Initialisation : on vérifie que P(n₀) est vraie, généralement pour n₀ = 0 ou n₀ = 1. C'est souvent la partie la plus rapide, mais elle est indispensable.
Hérédité : on suppose que P(n) est vraie pour un entier n ≥ n₀ quelconque (c'est l'hypothèse de récurrence), et on démontre qu'alors P(n+1) est vraie.
Conclusion : puisque la propriété est initialisée et héréditaire, le principe de récurrence permet d'affirmer qu'elle est vraie pour tout entier n ≥ n₀.
Ces trois étapes forment un tout indissociable. L'initialisation sans l'hérédité ne prouve rien au-delà du premier rang ; l'hérédité sans l'initialisation ne prouve rien du tout, car la chaîne d'implications n'a alors aucun point de départ. Il faut les deux pour que la démonstration tienne.
La rédaction type d'une démonstration par récurrence
Aux concours comme au bac, la forme compte autant que le fond. Une démonstration par récurrence bien rédigée suit toujours le même canevas, que l'on peut apprendre par cœur et adapter.
Le canevas à reproduire 1) « Montrons par récurrence que, pour tout n ≥ n₀, P(n) est vraie, où P(n) : … » — on énonce clairement la propriété. 2) « Initialisation : pour n = n₀, … donc P(n₀) est vraie. » 3) « Hérédité : soit n ≥ n₀ tel que P(n) est vraie (hypothèse de récurrence). Montrons P(n+1). … donc P(n+1) est vraie. » 4) « Conclusion : par le principe de récurrence, P(n) est vraie pour tout n ≥ n₀. » |
Deux réflexes de rédaction font gagner des points. D'abord, énoncer explicitement la propriété P(n) : le correcteur doit savoir exactement ce que l'on démontre. Ensuite, au moment de l'hérédité, dire clairement où l'on utilise l'hypothèse de récurrence. C'est le cœur de la preuve : si l'hypothèse ne sert jamais, c'est le signe que quelque chose ne va pas.
Exemple corrigé : somme des n premiers entiers
L'exemple canonique, à savoir refaire les yeux fermés, est la formule donnant la somme des n premiers entiers.
Pour tout n ≥ 1 : 1 + 2 + 3 + … + n = n(n + 1) / 2
Initialisation. Pour n = 1, le membre de gauche vaut 1 et le membre de droite vaut 1 × 2 / 2 = 1. Les deux sont égaux, donc P(1) est vraie.
Hérédité. Soit n ≥ 1 tel que 1 + 2 + … + n = n(n + 1)/2 (hypothèse de récurrence). Montrons P(n+1). On a 1 + 2 + … + n + (n+1) = n(n+1)/2 + (n+1) en utilisant l'hypothèse. En factorisant par (n+1) : (n+1)[n/2 + 1] = (n+1)(n+2)/2. C'est exactement la formule au rang n+1, donc P(n+1) est vraie.
Conclusion. Par le principe de récurrence, la formule 1 + 2 + … + n = n(n+1)/2 est vraie pour tout entier n ≥ 1.
Exemple corrigé : une inégalité (inégalité de Bernoulli)
La récurrence sert aussi à démontrer des inégalités. L'inégalité de Bernoulli en est l'exemple le plus classique.
Pour tout réel x ≥ −1 et tout entier n ≥ 0 : (1 + x)ⁿ ≥ 1 + nx
Initialisation. Pour n = 0, (1 + x)⁰ = 1 et 1 + 0 × x = 1. On a bien 1 ≥ 1, donc P(0) est vraie.
Hérédité. Supposons (1 + x)ⁿ ≥ 1 + nx pour un entier n ≥ 0. Comme x ≥ −1, le facteur (1 + x) est positif ou nul ; on peut donc multiplier l'inégalité par (1 + x) sans en changer le sens : (1 + x)ⁿ⁺¹ ≥ (1 + nx)(1 + x) = 1 + (n+1)x + nx². Or nx² ≥ 0, donc (1 + x)ⁿ⁺¹ ≥ 1 + (n+1)x. P(n+1) est vraie.
Conclusion. Par récurrence, (1 + x)ⁿ ≥ 1 + nx pour tout x ≥ −1 et tout n ≥ 0. On remarque au passage que l'hypothèse x ≥ −1 est cruciale : c'est elle qui autorise la multiplication de l'étape d'hérédité.
Exemple corrigé : une divisibilité
Les problèmes de divisibilité se prêtent particulièrement bien au raisonnement par récurrence.
Pour tout n ≥ 0 : 4ⁿ − 1 est divisible par 3
Initialisation. Pour n = 0, 4⁰ − 1 = 0, qui est divisible par 3 (0 = 3 × 0). P(0) est vraie.
Hérédité. Supposons que 4ⁿ − 1 est divisible par 3, c'est-à-dire 4ⁿ − 1 = 3k pour un entier k. Alors 4ⁿ⁺¹ − 1 = 4 × 4ⁿ − 1 = 4(3k + 1) − 1 = 12k + 3 = 3(4k + 1). C'est un multiple de 3, donc P(n+1) est vraie.
Conclusion. Par récurrence, 4ⁿ − 1 est divisible par 3 pour tout entier n ≥ 0. La technique récurrente ici consiste à faire apparaître l'expression du rang n (soit 4ⁿ − 1) dans celle du rang n+1, pour pouvoir appliquer l'hypothèse.
Exemple corrigé : la somme des carrés
Un autre grand classique, dont la formule est fréquemment demandée, est la somme des carrés des n premiers entiers. Elle illustre à nouveau la mécanique de l'hérédité, avec un calcul de factorisation un peu plus riche.
Pour tout n ≥ 1 : 1² + 2² + … + n² = n(n + 1)(2n + 1) / 6
Initialisation. Pour n = 1, le membre de gauche vaut 1² = 1 et le membre de droite vaut 1 × 2 × 3 / 6 = 1. Les deux coïncident, donc P(1) est vraie.
Hérédité. Supposons 1² + … + n² = n(n+1)(2n+1)/6. Alors 1² + … + n² + (n+1)² = n(n+1)(2n+1)/6 + (n+1)². On factorise par (n+1)/6 : (n+1)/6 · [n(2n+1) + 6(n+1)] = (n+1)/6 · [2n² + 7n + 6] = (n+1)(n+2)(2n+3)/6. C'est bien la formule au rang n+1, obtenue en remplaçant n par n+1. Donc P(n+1) est vraie.
Conclusion. Par récurrence, 1² + 2² + … + n² = n(n+1)(2n+1)/6 pour tout n ≥ 1. Le point délicat est ici la factorisation de l'expression obtenue après ajout de (n+1)² : c'est un savoir-faire calculatoire qui se travaille et qui distingue une hérédité aboutie d'une hérédité laissée en plan.
Ces deux formules — somme des entiers et somme des carrés — reviennent constamment dans les exercices d'analyse et de probabilités. Les connaître et savoir les redémontrer par récurrence est un investissement rentable : on gagne du temps le jour de l'épreuve et l'on sécurise des points de rigueur souvent négligés.
Récurrence simple, double et forte
La récurrence « ordinaire » n'est qu'une des formes possibles. Selon la propriété à démontrer, on adapte la structure de l'hérédité.
La récurrence simple
C'est la forme la plus courante, celle des exemples précédents : l'hérédité déduit P(n+1) de la seule hypothèse P(n). On n'utilise que le rang immédiatement précédent. C'est le cas par défaut, celui vers lequel on se tourne d'abord.
La récurrence double
Certaines suites sont définies à partir de leurs deux termes précédents (comme la suite de Fibonacci : uₙ₊₂ = uₙ₊₁ + uₙ). L'hérédité doit alors supposer P(n) et P(n+1) vraies pour en déduire P(n+2). Conséquence importante : l'initialisation doit vérifier deux rangs de départ, P(n₀) et P(n₀+1), pour amorcer correctement la chaîne.
La récurrence forte
Dans la récurrence forte (ou récurrence complète), l'hérédité suppose que la propriété est vraie pour tous les rangs de n₀ jusqu'à n, et non seulement au rang n, pour en déduire P(n+1). Elle est indispensable lorsque le passage au rang suivant fait intervenir un rang antérieur quelconque — par exemple pour démontrer que tout entier ≥ 2 admet un diviseur premier, ou pour certaines suites où uₙ₊₁ dépend de plusieurs termes précédents.
Type de récurrence | Hypothèse d'hérédité | Initialisation |
Simple | P(n) | P(n₀) |
Double | P(n) et P(n+1) | P(n₀) et P(n₀+1) |
Forte | P(k) pour tout n₀ ≤ k ≤ n | P(n₀) (parfois plusieurs rangs) |
Les trois grandes formes de récurrence : on adapte l'hypothèse et l'initialisation à la propriété.
Suites définies par récurrence
Le mot « récurrence » désigne aussi un mode de définition des suites : une suite définie par récurrence est donnée par un premier terme et une relation qui exprime chaque terme en fonction du précédent, du type uₙ₊₁ = f(uₙ). Le raisonnement par récurrence est alors l'outil naturel pour en étudier les propriétés (bornes, monotonie, signe, formule explicite).
Exemple. Soit la suite définie par u₀ = 2 et uₙ₊₁ = (uₙ + 3)/2. Montrons par récurrence que pour tout n, 2 ≤ uₙ ≤ 3. Initialisation : u₀ = 2 vérifie 2 ≤ 2 ≤ 3. Hérédité : si 2 ≤ uₙ ≤ 3, alors 5 ≤ uₙ + 3 ≤ 6, donc 2,5 ≤ (uₙ+3)/2 ≤ 3, et a fortiori 2 ≤ uₙ₊₁ ≤ 3. La propriété est donc vraie pour tout n : la suite est bien encadrée entre 2 et 3.
Récurrence et étude de suites Pour montrer qu'une suite définie par uₙ₊₁ = f(uₙ) reste dans un intervalle, ou qu'elle est monotone, la récurrence est presque toujours la bonne méthode. On suppose la propriété au rang n, puis on l'utilise sur uₙ₊₁ = f(uₙ) en exploitant les variations de f. |
Exemple corrigé : une récurrence forte
Voici une situation où la récurrence simple ne suffit pas et où la récurrence forte s'impose. On considère la suite définie par u₀ = 3, u₁ = 5 et, pour tout n ≥ 0, uₙ₊₂ = 3uₙ₊₁ − 2uₙ. Montrons que pour tout n, uₙ = 2ⁿ⁺¹ + 1.
Initialisation. Pour n = 0, 2¹ + 1 = 3 = u₀ ; pour n = 1, 2² + 1 = 5 = u₁. La relation faisant intervenir les deux rangs précédents, on vérifie bien les deux premiers rangs.
Hérédité. Supposons la formule vraie jusqu'au rang n+1, c'est-à-dire uₙ = 2ⁿ⁺¹ + 1 et uₙ₊₁ = 2ⁿ⁺² + 1. Alors uₙ₊₂ = 3uₙ₊₁ − 2uₙ = 3(2ⁿ⁺² + 1) − 2(2ⁿ⁺¹ + 1) = 3·2ⁿ⁺² + 3 − 2ⁿ⁺² − 2 = 2·2ⁿ⁺² + 1 = 2ⁿ⁺³ + 1. C'est la formule au rang n+2, donc elle est héréditaire.
Conclusion. Par récurrence (double ici, forte dans le principe), uₙ = 2ⁿ⁺¹ + 1 pour tout entier n. On voit pourquoi il fallait supposer deux rangs à la fois : la relation de récurrence relie chaque terme à ses deux prédécesseurs, et l'hypothèse portant sur un seul rang aurait été insuffisante.
Récurrence et démonstration d'une formule explicite
Une utilisation très fréquente de la récurrence consiste à démontrer qu'une suite définie « de proche en proche » possède une formule explicite (une expression directe de uₙ en fonction de n). La méthode est toujours la même : on conjecture la formule en calculant les premiers termes, puis on la démontre par récurrence.
Exemple. Soit la suite définie par v₀ = 1 et vₙ₊₁ = 2vₙ + 1. En calculant v₀ = 1, v₁ = 3, v₂ = 7, v₃ = 15, on conjecture vₙ = 2ⁿ⁺¹ − 1. Initialisation : v₀ = 2¹ − 1 = 1, correct. Hérédité : si vₙ = 2ⁿ⁺¹ − 1, alors vₙ₊₁ = 2(2ⁿ⁺¹ − 1) + 1 = 2ⁿ⁺² − 2 + 1 = 2ⁿ⁺² − 1, ce qui est la formule au rang n+1. La formule explicite est donc démontrée pour tout n.
La démarche « conjecturer puis démontrer » Face à une suite récurrente, calculer les premiers termes permet souvent de deviner la formule explicite. Mais deviner ne suffit pas : seule une démonstration par récurrence transforme la conjecture en résultat certain. C'est un réflexe attendu au bac comme aux concours. |
Erreurs classiques à éviter
La récurrence est une mécanique précise : les fautes viennent presque toujours d'un maillon négligé de la chaîne.
Oublier l'initialisation : c'est l'erreur la plus fréquente. Sans premier domino, rien ne tombe. Une hérédité seule ne prouve absolument rien.
Mal poser l'hérédité : il faut supposer P(n) et démontrer P(n+1), pas l'inverse. Confondre l'hypothèse et la conclusion est une faute de logique grave.
Ne jamais utiliser l'hypothèse de récurrence : si la preuve du rang n+1 n'emploie pas P(n), c'est qu'une récurrence était inutile — ou que la démonstration est fausse.
Initialiser au mauvais rang : la propriété doit être initialisée au premier rang concerné (n₀). Pour une récurrence double, il faut deux rangs de départ.
Rédiger sans énoncer P(n) : ne pas dire clairement quelle propriété on démontre rend la copie illisible et coûte des points.
Conclusion
Le raisonnement par récurrence est l'un des outils les plus puissants et les plus élégants des mathématiques : il transforme une infinité de vérifications en trois étapes bien délimitées. Initialisation, hérédité, conclusion : ce triptyque, une fois maîtrisé, permet de démontrer des formules, des inégalités, des divisibilités et d'étudier les suites avec une rigueur imparable.
La clé est la discipline de rédaction. En énonçant clairement la propriété, en vérifiant soigneusement l'initialisation et en identifiant précisément l'endroit où l'hypothèse de récurrence sert, on évite les pièges les plus courants. De la terminale aux concours, la démonstration par récurrence reste un réflexe qui rapporte : celui de la rangée de dominos qui, une fois lancée, ne s'arrête jamais.
