Récurrence : comprendre pourquoi ça marche et savoir la rédiger
La récurrence intimide souvent parce qu'on l'apprend comme une recette : trois étapes à réciter, une hypothèse mystérieuse que l'on « suppose vraie ».
ViragePrépa
La récurrence intimide souvent parce qu'on l'apprend comme une recette : trois étapes à réciter, une hypothèse mystérieuse que l'on « suppose vraie ». Pourtant, dès qu'on en saisit le mécanisme profond, elle devient limpide et presque évidente. Démontrer par récurrence, c'est prouver une infinité d'affirmations d'un seul geste, en s'appuyant sur une idée que chacun connaît intuitivement : celle d'une réaction en chaîne.
L'enjeu, en terminale comme en prépa, n'est pas seulement de connaître les trois étapes, mais de comprendre pourquoi elles suffisent et de savoir les rédiger sans faille. C'est cet angle que privilégie ce cours : d'abord l'intuition et la logique qui rendent la récurrence valide, ensuite un canevas de rédaction précis, puis des exemples corrigés couvrant tous les cas de figure. L'objectif est simple : que la récurrence devienne un automatisme fiable, et non une source d'angoisse.
Comprendre la récurrence : l'idée de la réaction en chaîne
Imaginons une file infinie de dominos alignés. On veut être certain qu'ils tomberont tous. Les vérifier un par un est impossible : ils sont en nombre infini. Mais deux constats suffisent. D'abord, on pousse le premier et l'on constate qu'il tombe. Ensuite, on remarque que les dominos sont assez rapprochés pour que chacun, en tombant, renverse le suivant. Ces deux faits garantissent, sans rien vérifier d'autre, que toute la file s'effondrera.
La récurrence formalise exactement cette intuition. La propriété à démontrer joue le rôle des dominos ; « le domino n tombe » se traduit par « la propriété est vraie au rang n ». Pousser le premier domino, c'est l'initialisation. Garantir que chaque domino renverse le suivant, c'est l'hérédité. Et la conclusion — tous les dominos tombent — devient : la propriété est vraie pour tout entier.
P(n₀) vraie et pour tout n ≥ n₀, P(n) ⇒ P(n+1) ⟹ P(n) vraie pour tout n ≥ n₀
Ce qu'il faut vraiment comprendre, c'est pourquoi ces deux conditions suffisent. Prenons un entier quelconque, disons 100. Pourquoi P(100) est-elle vraie ? Parce que P(0) l'est (initialisation), et que l'hérédité, appliquée cent fois de suite, propage la vérité de P(0) à P(1), puis de P(1) à P(2), et ainsi de suite jusqu'à P(100). Pour n'importe quel entier fixé, il existe un chemin fini d'implications qui y mène depuis le départ. C'est cette propagation « de proche en proche » qui fonde toute la méthode.
L'hypothèse de récurrence n'est pas une pétition de principe
Le point qui déroute le plus les débutants : au moment de l'hérédité, on « suppose P(n) vraie ». N'est-ce pas supposer ce que l'on cherche à démontrer ? Non, et la distinction est capitale. On ne suppose pas que P(n) est vraie pour tous les n — ce serait la conclusion. On suppose seulement que, pour un rang n donné, si la propriété y était vraie, alors elle le serait au rang suivant. On démontre une implication conditionnelle, pas la propriété elle-même. C'est la répétition de cette implication, combinée à l'initialisation, qui produit le résultat.
Les trois étapes, et ce que chacune garantit
Initialisation : on vérifie que P(n₀) est vraie, le plus souvent pour n₀ = 0 ou n₀ = 1. C'est le premier domino ; sans lui, rien ne tombe.
Hérédité : on suppose P(n) vraie à un rang n ≥ n₀ quelconque (hypothèse de récurrence) et l'on démontre que P(n+1) l'est aussi. C'est la garantie que chaque domino renverse le suivant.
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 n ≥ n₀.
Les deux briques sont indissociables L'hérédité sans l'initialisation ne prouve rien : une propriété fausse peut très bien être « héréditaire » (par exemple « 2 divise 2n+1 » : si c'était vrai au rang n, ce le serait au rang n+1… sauf que ce n'est jamais vrai). L'initialisation sans l'hérédité ne prouve la propriété qu'au premier rang. Il faut impérativement les deux. |
Rédiger une récurrence : le canevas à reproduire
Au bac comme aux concours, la rédaction est notée pour elle-même. Une récurrence bien rédigée suit toujours la même trame, que l'on peut mémoriser et décliner sur n'importe quel énoncé.
Le canevas type 1) « Montrons par récurrence que, pour tout n ≥ n₀, P(n) est vraie, où P(n) : … » — on énonce la propriété noir sur blanc. 2) « Initialisation : pour n = n₀, … donc P(n₀) est vraie. » 3) « Hérédité : soit n ≥ n₀ tel que P(n) est vraie. Montrons que P(n+1) l'est. … donc P(n+1) est vraie. » 4) « Conclusion : d'après le principe de récurrence, P(n) est vraie pour tout n ≥ n₀. » |
Trois réflexes de rédaction rapportent des points à chaque copie. Premièrement, énoncer explicitement P(n) : le correcteur doit voir précisément ce que l'on démontre. Deuxièmement, au moment de l'hérédité, signaler l'endroit exact où l'on utilise l'hypothèse de récurrence (« d'après l'hypothèse de récurrence… ») : c'est le cœur logique de la preuve. Troisièmement, conclure explicitement en invoquant le principe de récurrence, sans se contenter d'un vague « donc c'est vrai ».
Un signal d'alarme utile Si, en rédigeant l'hérédité, vous n'utilisez jamais l'hypothèse de récurrence, c'est presque toujours mauvais signe : soit la récurrence est inutile (la propriété se démontrait directement), soit votre preuve est fausse. L'hypothèse doit servir. |
Exemple corrigé : somme des n premiers nombres impairs
Un premier exemple, aussi élégant que formateur : la somme des n premiers nombres impairs vaut exactement n². On énonce P(n) : 1 + 3 + 5 + … + (2n − 1) = n².
Pour tout n ≥ 1 : 1 + 3 + 5 + … + (2n − 1) = n²
Initialisation. Pour n = 1, la somme se réduit au premier terme, 1, et n² = 1² = 1. Les deux membres valent 1, donc P(1) est vraie.
Hérédité. Soit n ≥ 1 tel que 1 + 3 + … + (2n − 1) = n² (hypothèse de récurrence). Au rang n+1, on ajoute le terme suivant, 2(n+1) − 1 = 2n + 1 : 1 + 3 + … + (2n − 1) + (2n + 1) = n² + (2n + 1) d'après l'hypothèse. Or n² + 2n + 1 = (n + 1)². On obtient donc (n+1)², ce qui est la formule au rang n+1. P(n+1) est vraie.
Conclusion. Par le principe de récurrence, la somme des n premiers nombres impairs vaut n² pour tout entier n ≥ 1. On note au passage la mécanique universelle de l'hérédité : faire apparaître la somme du rang n dans celle du rang n+1 pour y injecter l'hypothèse.
Exemple corrigé : une somme géométrique
La récurrence permet aussi d'établir la formule de la somme des puissances d'un réel, très employée par la suite. On fixe un réel q ≠ 1 et l'on pose P(n).
Pour tout n ≥ 0 : 1 + q + q² + … + qⁿ = (qⁿ⁺¹ − 1) / (q − 1)
Initialisation. Pour n = 0, le membre de gauche vaut 1 (un seul terme, q⁰) et le membre de droite vaut (q¹ − 1)/(q − 1) = 1. Égalité vérifiée, donc P(0) est vraie.
Hérédité. Supposons 1 + q + … + qⁿ = (qⁿ⁺¹ − 1)/(q − 1). En ajoutant qⁿ⁺¹ aux deux membres : 1 + q + … + qⁿ + qⁿ⁺¹ = (qⁿ⁺¹ − 1)/(q − 1) + qⁿ⁺¹. On réduit au même dénominateur : [qⁿ⁺¹ − 1 + qⁿ⁺¹(q − 1)]/(q − 1) = [qⁿ⁺¹ − 1 + qⁿ⁺² − qⁿ⁺¹]/(q − 1) = (qⁿ⁺² − 1)/(q − 1). C'est la formule au rang n+1. P(n+1) est vraie.
Conclusion. Par récurrence, la formule est vraie pour tout n ≥ 0. L'hypothèse q ≠ 1 est essentielle : elle assure que le dénominateur q − 1 n'est jamais nul.
Exemple corrigé : une inégalité
Les inégalités se prêtent bien à la récurrence, à condition de manier les majorations avec soin. Montrons que 2ⁿ dépasse n dès que n vaut au moins 1.
Pour tout n ≥ 1 : 2ⁿ > n
Initialisation. Pour n = 1, 2¹ = 2 et 2 > 1. Donc P(1) est vraie.
Hérédité. Supposons 2ⁿ > n pour un entier n ≥ 1. Alors 2ⁿ⁺¹ = 2 × 2ⁿ > 2n d'après l'hypothèse. Or, pour n ≥ 1, on a 2n = n + n ≥ n + 1. Donc 2ⁿ⁺¹ > 2n ≥ n + 1, ce qui donne 2ⁿ⁺¹ > n + 1. P(n+1) est vraie.
Conclusion. Par récurrence, 2ⁿ > n pour tout n ≥ 1. La difficulté d'une récurrence sur une inégalité tient à l'enchaînement des majorations : il faut relier ce que donne l'hypothèse (ici 2n) à ce que l'on veut prouver (n + 1), grâce à une inégalité intermédiaire.
Exemple corrigé : une divisibilité
La récurrence est l'outil naturel des problèmes de divisibilité. Montrons que 3²ⁿ − 1 est divisible par 8 pour tout entier n.
Pour tout n ≥ 0 : 3²ⁿ − 1 est divisible par 8
Initialisation. Pour n = 0, 3⁰ − 1 = 0, et 0 = 8 × 0 est bien divisible par 8. P(0) est vraie.
Hérédité. Supposons 3²ⁿ − 1 = 8k pour un entier k, soit 3²ⁿ = 8k + 1. Alors 3²⁽ⁿ⁺¹⁾ − 1 = 3²ⁿ⁺² − 1 = 9 × 3²ⁿ − 1 = 9(8k + 1) − 1 = 72k + 9 − 1 = 72k + 8 = 8(9k + 1). C'est un multiple de 8, donc P(n+1) est vraie.
Conclusion. Par récurrence, 3²ⁿ − 1 est divisible par 8 pour tout n ≥ 0. Le geste clé consiste à écrire 3²ⁿ⁺² = 9 × 3²ⁿ pour faire réapparaître le terme du rang n et exploiter l'hypothèse.
Récurrence simple, double et forte
La récurrence « ordinaire » n'est qu'une des formes disponibles. Selon la façon dont le rang n+1 dépend des rangs précédents, on ajuste l'hypothèse et l'initialisation.
La récurrence simple
C'est la forme par défaut, celle des exemples ci-dessus : 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.
La récurrence double
Quand une suite est définie par ses deux termes précédents (relation du type uₙ₊₂ = a·uₙ₊₁ + b·uₙ), l'hérédité doit supposer P(n) et P(n+1) pour en déduire P(n+2). Conséquence : l'initialisation vérifie deux rangs de départ, P(n₀) et P(n₀+1).
La récurrence forte
Dans la récurrence forte (ou complète), l'hérédité suppose la propriété vraie pour tous les rangs de n₀ jusqu'à n, et pas seulement au rang n, pour en déduire P(n+1). Elle s'impose quand le passage au rang suivant fait intervenir un rang antérieur quelconque — par exemple pour prouver que tout entier ≥ 2 possède un diviseur premier.
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 formes de récurrence : on adapte l'hypothèse et l'initialisation à la structure de l'énoncé.
Exemple corrigé : suite définie par récurrence
Le mot « récurrence » désigne aussi un mode de définition des suites : chaque terme s'exprime à partir du précédent, du type uₙ₊₁ = f(uₙ). Le raisonnement par récurrence sert alors à en étudier les propriétés (bornes, monotonie). Prenons la suite définie par u₀ = 1 et uₙ₊₁ = √(uₙ + 2), et montrons que pour tout n, 0 ≤ uₙ ≤ 2.
Initialisation. u₀ = 1 vérifie bien 0 ≤ 1 ≤ 2. Donc P(0) est vraie.
Hérédité. Supposons 0 ≤ uₙ ≤ 2. En ajoutant 2 : 2 ≤ uₙ + 2 ≤ 4. En passant à la racine carrée (fonction croissante) : √2 ≤ √(uₙ + 2) ≤ 2, c'est-à-dire √2 ≤ uₙ₊₁ ≤ 2. Or √2 ≥ 0, donc a fortiori 0 ≤ uₙ₊₁ ≤ 2. P(n+1) est vraie.
Conclusion. Par récurrence, 0 ≤ uₙ ≤ 2 pour tout entier n : la suite est bornée. On exploite ici la croissance de la fonction racine pour transporter l'encadrement du rang n au rang n+1.
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 s'appuyant sur les variations de f. |
Exemple corrigé : une récurrence forte
Voici un cas où la récurrence simple échoue et où la récurrence forte s'impose. On considère la suite définie par u₀ = 1, u₁ = 2 et uₙ₊₂ = 3uₙ₊₁ − 2uₙ. Montrons que pour tout n, uₙ = 2ⁿ.
Initialisation. Pour n = 0, 2⁰ = 1 = u₀ ; pour n = 1, 2¹ = 2 = u₁. La relation reliant chaque terme à ses deux prédécesseurs, on vérifie les deux premiers rangs.
Hérédité. Supposons la formule vraie jusqu'au rang n+1, soit uₙ = 2ⁿ et uₙ₊₁ = 2ⁿ⁺¹. Alors uₙ₊₂ = 3uₙ₊₁ − 2uₙ = 3 × 2ⁿ⁺¹ − 2 × 2ⁿ = 3 × 2ⁿ⁺¹ − 2ⁿ⁺¹ = 2 × 2ⁿ⁺¹ = 2ⁿ⁺². C'est la formule au rang n+2, donc elle est héréditaire.
Conclusion. Par récurrence (à deux rangs), uₙ = 2ⁿ pour tout entier n. On voit pourquoi il fallait supposer deux rangs à la fois : la relation relie chaque terme à ses deux prédécesseurs, et une hypothèse sur un seul rang aurait été insuffisante pour conclure.
Conjecturer puis démontrer une formule explicite
Une utilisation très courante de la récurrence consiste à trouver la formule explicite d'une suite définie de proche en proche, c'est-à-dire une expression directe de uₙ en fonction de n. La démarche se fait en deux temps : on calcule les premiers termes pour deviner la formule, puis on la démontre par récurrence pour en être certain.
Exemple. Soit la suite définie par v₀ = 1 et vₙ₊₁ = 2vₙ + 3. On calcule v₀ = 1, v₁ = 5, v₂ = 13, v₃ = 29. En observant que chaque terme augmenté de 3 donne 4, 8, 16, 32, soit des puissances de 2, on conjecture vₙ = 2ⁿ⁺² − 3.
Initialisation. Pour n = 0, 2⁰⁺² − 3 = 4 − 3 = 1 = v₀. La formule est vraie au premier rang.
Hérédité. Supposons vₙ = 2ⁿ⁺² − 3. Alors vₙ₊₁ = 2vₙ + 3 = 2(2ⁿ⁺² − 3) + 3 = 2ⁿ⁺³ − 6 + 3 = 2ⁿ⁺³ − 3. C'est bien la formule au rang n+1 (on a remplacé n par n+1), donc P(n+1) est vraie.
Conclusion. Par récurrence, vₙ = 2ⁿ⁺² − 3 pour tout entier n. La conjecture est ainsi transformée en résultat certain.
Deviner ne suffit pas Calculer les premiers termes permet souvent de deviner la formule explicite, mais une conjecture n'est pas une preuve. Seule la démonstration par récurrence garantit qu'elle est vraie pour tous les entiers, y compris ceux qu'on n'a pas calculés. C'est un réflexe attendu au bac comme aux concours. |
Erreurs classiques à éviter
Les fautes de récurrence viennent presque toujours d'un maillon négligé de la chaîne ou d'une rédaction imprécise.
Oublier l'initialisation : l'erreur la plus fréquente et la plus coûteuse. Sans premier domino, la propriété n'est démontrée nulle part.
Inverser hypothèse et conclusion : on suppose P(n) et l'on démontre P(n+1), jamais l'inverse. Confondre les deux est une faute de logique majeure.
Ne pas utiliser l'hypothèse de récurrence : si l'hérédité ne s'en sert pas, la récurrence est inutile ou la preuve est fausse.
Initialiser au mauvais rang : la propriété doit être initialisée au premier rang concerné ; pour une récurrence double, il faut deux rangs de départ.
Oublier d'énoncer P(n) : sans propriété clairement écrite, le correcteur ne peut pas suivre, et la copie perd des points de rigueur.
Croire qu'une propriété héréditaire est forcément vraie : sans initialisation valide, l'hérédité seule ne prouve rien du tout.
Conclusion
La récurrence cesse d'intimider dès qu'on la comprend pour ce qu'elle est : une réaction en chaîne rigoureuse. Deux briques suffisent — l'initialisation, qui pousse le premier domino, et l'hérédité, qui garantit que chacun renverse le suivant. Ensemble, elles démontrent une infinité d'affirmations d'un seul mouvement, avec une économie de moyens saisissante.
Comprendre le mécanisme et maîtriser le canevas de rédaction sont les deux faces d'un même savoir-faire. En énonçant clairement la propriété, en vérifiant l'initialisation, en signalant précisément où l'hypothèse de récurrence intervient et en concluant par le principe de récurrence, on transforme une méthode redoutée en un réflexe sûr — de la terminale jusqu'aux concours.
