Rédigé et vérifié par un professeur diplômé de l’École Polytechnique. Découvrir le professeur
Tu sais démontrer une propriété « à la main » sur un ou deux cas, mais dès qu’il faut la prouver pour tout entier, tu bloques ? C’est exactement là qu’intervient la récurrence. Le vrai enjeu n’est pas de comprendre le principe (il est simple), mais de le rédiger proprement : c’est là que se jouent les points au bac et en colle. Voici la méthode en 3 étapes, avec des exemples résolus, les erreurs qui coûtent des points et des exercices corrigés.
I. Le principe de récurrence en une image
Avant de rédiger, il faut avoir en tête ce qui « fait marcher » une récurrence. Imagine une rangée infinie de dominos. Pour être sûr qu’ils tombent tous, il te suffit de vérifier deux choses.
Le premier domino doit tomber (c’est l’initialisation), et chaque domino qui tombe doit faire tomber le suivant (c’est l’hérédité). Ces deux conditions suffisent : tous les dominos tombent. C’est tout le principe de récurrence.
Principe de récurrence
Soit \(P(n)\) une propriété dépendant d’un entier \(n\). Si :
1. \(P(n_0)\) est vraie (initialisation au rang \(n_0\)) ;
2. pour tout entier \(n \geq n_0\), \(P(n) \Rightarrow P(n+1)\) (hérédité) ;
alors \(P(n)\) est vraie pour tout entier \(n \geq n_0\).
Cette page se concentre sur la rédaction. Si tu veux d’abord comprendre en profondeur d’où vient ce principe, ses variantes et son histoire, consulte le cours complet sur le raisonnement par récurrence.
II. Quand utiliser une récurrence (et quand ne pas le faire)
La récurrence n’est pas toujours la bonne technique. Elle sert quand une propriété dépend d’un entier \(n\) et qu’on peut relier le cas \(n+1\) au cas \(n\). Voici comment la situer par rapport aux autres méthodes de démonstration que tu croises en Terminale et en prépa.
| Méthode | Quand l’utiliser | Signal déclencheur |
|---|---|---|
| Preuve directe | Une formule ou un calcul suffit, sans dépendance à un rang précédent | « Montrer que \(f\) est croissante » |
| Récurrence simple | La propriété au rang \(n+1\) se déduit de celle au rang \(n\) | « Pour tout \(n \in \mathbb{N}\)… », sommes, \(u_{n+1}=f(u_n)\) |
| Récurrence forte | On a besoin de tous les rangs précédents, pas seulement du rang \(n\) | Suites définies par \(u_{n+1}\) en fonction de plusieurs termes (voir récurrence forte) |
| Récurrence double | Le rang \(n+1\) dépend de \(n\) et de \(n-1\) | Suite de Fibonacci, \(u_{n+2}=au_{n+1}+bu_n\) |
| Raisonnement par l’absurde | On veut montrer une impossibilité ou une unicité | « Montrer qu’il n’existe pas… » |
Le réflexe qui ne trompe pas : si l’énoncé contient « pour tout entier \(n\) » et que tu vois comment écrire le rang \(n+1\) à partir du rang \(n\), pense récurrence. Si tu as besoin de plusieurs termes précédents à la fois, passe à la récurrence forte ou double.
Une fois la récurrence simple identifiée, il ne reste qu’à la rédiger. C’est le cœur de cet article.
La méthode complète de la récurrence en une fiche recto-verso
Les 3 étapes, les phrases-types à recopier et les erreurs à éviter, prêtes à glisser dans ton classeur avant le prochain DS.
📄 Télécharger la fiche méthodeGagne des points en rédigeant proprement dès la prochaine copie.
III. La méthode en 3 étapes
Toute récurrence bien rédigée suit exactement la même trame. Apprends-la comme une routine : c’est ce que le correcteur veut voir apparaître, dans cet ordre.
Étape 0 — Définir la propriété \(P(n)\)
Avant même de commencer, écris noir sur blanc la propriété que tu vas démontrer. C’est l’étape que 90 % des élèves oublient, et c’est pourtant elle qui structure toute la copie.
À écrire : « Pour tout entier \(n \geq n_0\), on note \(P(n)\) la propriété : … ». La propriété doit être une phrase vraie ou fausse pour un \(n\) donné, pas un calcul.
Étape 1 — L’initialisation
Tu vérifies que la propriété est vraie au premier rang \(n_0\) (souvent \(n_0 = 0\) ou \(n_0 = 1\)). Concrètement : tu remplaces \(n\) par \(n_0\) des deux côtés et tu vérifies l’égalité (ou l’inégalité).
À écrire : « Initialisation : pour \(n = n_0\), … donc \(P(n_0)\) est vraie. »
Étape 2 — L’hérédité
C’est l’étape la plus riche. Tu supposes la propriété vraie à un rang \(n\) fixé (c’est l’hypothèse de récurrence), puis tu démontres qu’elle est encore vraie au rang \(n+1\).
À écrire : « Hérédité : soit \(n \geq n_0\) un entier fixé. Supposons \(P(n)\) vraie (hypothèse de récurrence). Montrons alors \(P(n+1)\). » Puis tu pars de ce que tu veux prouver au rang \(n+1\) et tu fais apparaître l’hypothèse de récurrence dans ton calcul.
Étape 3 — La conclusion
Tu invoques le principe de récurrence pour conclure. Une seule phrase suffit, mais elle est obligatoire.
À écrire : « Conclusion : \(P(n_0)\) est vraie et \(P\) est héréditaire, donc d’après le principe de récurrence, \(P(n)\) est vraie pour tout entier \(n \geq n_0\). »
Retiens cette trame — Définir, Initialiser, Hériter, Conclure — et applique-la à la lettre. Passons maintenant aux exemples résolus.
IV. Trois exemples résolus, du simple au technique
Exemple 1 — Une somme 🟢 Lycée
Énoncé : démontrer que pour tout entier \(n \geq 1\), \(\displaystyle\sum_{k=1}^{n} k = \displaystyle\frac{n(n+1)}{2}\).
Propriété. Pour tout \(n \geq 1\), on note \(P(n)\) : \(\displaystyle 1 + 2 + \cdots + n = \displaystyle\frac{n(n+1)}{2}\).
Initialisation. Pour \(n = 1\) : à gauche \(1\), à droite \(\displaystyle\frac{1 \times 2}{2} = 1\). Donc \(P(1)\) est vraie.
Hérédité. Soit \(n \geq 1\) fixé. Supposons \(P(n)\) vraie. Alors :
\(\displaystyle \sum_{k=1}^{n+1} k = \left(\sum_{k=1}^{n} k\right) + (n+1) = \displaystyle\frac{n(n+1)}{2} + (n+1)\)
où l’on a utilisé l’hypothèse de récurrence. En factorisant par \(n+1\) :
\(\displaystyle\frac{n(n+1)}{2} + (n+1) = (n+1)\left(\displaystyle\frac{n}{2}+1\right) = \displaystyle\frac{(n+1)(n+2)}{2}\)
C’est bien \(P(n+1)\). La propriété est héréditaire.
Conclusion. \(P(1)\) est vraie et \(P\) est héréditaire, donc \(P(n)\) est vraie pour tout \(n \geq 1\). ∎
Toute la méthode récurrence sur une fiche à imprimer
Les phrases-types de l’initialisation, de l’hérédité et de la conclusion, avec un exemple modèle entièrement rédigé.
📄 Récupérer la fiche méthodeRecopie la bonne trame et ne perds plus jamais de points de rédaction.
Exemple 2 — Une inégalité 🟢 Lycée
Énoncé : démontrer que pour tout entier \(n \geq 0\), \(2^n\) > \(n\).
Propriété. Pour tout \(n \geq 0\), on note \(P(n)\) : \(2^n\) > \(n\).
Initialisation. Pour \(n = 0\) : \(2^0 = 1\) > \(0\). Donc \(P(0)\) est vraie.
Hérédité. Soit \(n \geq 0\) fixé. Supposons \(2^n\) > \(n\). Alors :
\(2^{n+1} = 2 \times 2^n\) > \(2n\) (d’après l’hypothèse de récurrence).
Or, pour \(n \geq 0\), on a \(2n = n + n \geq n + 0\), et plus précisément \(2n \geq n+1\) dès que \(n \geq 1\). On vérifie à part le passage de \(0\) à \(1\) : \(2^1 = 2\) > \(1\). Ainsi \(2^{n+1}\) > \(n+1\), donc \(P(n+1)\) est vraie.
Conclusion. D’après le principe de récurrence, \(2^n\) > \(n\) pour tout \(n \geq 0\). ∎
Pour les inégalités plus fines, tu croiseras l’inégalité de Bernoulli, traitée dans les exercices corrigés de récurrence.
Exemple 3 — Une divisibilité 🟡 Avancé
Énoncé : démontrer que pour tout entier \(n \geq 0\), \(4^n - 1\) est divisible par \(3\).
Propriété. Pour tout \(n \geq 0\), on note \(P(n)\) : il existe un entier \(k\) tel que \(4^n - 1 = 3k\).
Initialisation. Pour \(n = 0\) : \(4^0 - 1 = 0 = 3 \times 0\). Donc \(P(0)\) est vraie.
Hérédité. Soit \(n \geq 0\) fixé. Supposons qu’il existe un entier \(k\) tel que \(4^n - 1 = 3k\), donc \(4^n = 3k + 1\). Alors :
\(4^{n+1} - 1 = 4 \times 4^n - 1 = 4(3k+1) - 1 = 12k + 3 = 3(4k+1)\)
Comme \(4k+1\) est un entier, \(4^{n+1}-1\) est divisible par \(3\), donc \(P(n+1)\) est vraie.
Conclusion. D’après le principe de récurrence, \(4^n - 1\) est divisible par \(3\) pour tout \(n \geq 0\). ∎
V. Les 4 erreurs qui coûtent des points
Une récurrence juste sur le fond mais mal rédigée perd des points. Voici les fautes les plus fréquentes, avec la copie fautive et sa correction.
Erreur 1 — Oublier l’initialisation
❌ Copie fautive : « Supposons \(P(n)\) vraie, montrons \(P(n+1)\)… » (et rien avant).
Diagnostic : sans initialisation, l’hérédité est inutile. Une propriété peut être héréditaire tout en étant fausse partout (ex : \(2^n = 2^{n+1}\) est héréditaire mais jamais vraie).
✅ Correction : toujours commencer par vérifier \(P(n_0)\), même si c’est « évident ».
Erreur 2 — Supposer ce qu’on veut démontrer
❌ Copie fautive : « Supposons que pour tout \(n\), \(P(n)\) est vraie… »
Diagnostic : c’est un cercle vicieux : tu supposes précisément ce que tu dois prouver. L’hypothèse de récurrence porte sur un entier \(n\) fixé, pas sur tous.
✅ Correction : « Soit \(n \geq n_0\) fixé. Supposons \(P(n)\) vraie. »
Erreur 3 — Ne jamais utiliser l’hypothèse de récurrence
❌ Copie fautive : une démonstration de \(P(n+1)\) qui ne mentionne jamais \(P(n)\).
Diagnostic : si tu prouves \(P(n+1)\) directement sans utiliser \(P(n)\), c’est que ce n’est pas une récurrence… ou que tu t’es trompé. Le moment clé de l’hérédité est celui où tu remplaces une expression par l’hypothèse.
✅ Correction : encadre ou souligne l’endroit où tu écris « d’après l’hypothèse de récurrence ».
Erreur 4 — Oublier la phrase de conclusion
❌ Copie fautive : s’arrêter juste après avoir prouvé \(P(n+1)\).
Diagnostic : initialisation + hérédité ne concluent pas d’elles-mêmes. C’est le principe de récurrence qui te donne le droit de conclure « pour tout \(n\) ».
✅ Correction : termine toujours par la phrase invoquant le principe de récurrence.
Ces réflexes acquis, entraîne-toi sur les exercices suivants.
VI. Exercices d’application corrigés
Exercice 1 (★). Démontrer que pour tout entier \(n \geq 1\), \(\displaystyle\sum_{k=1}^{n} (2k-1) = n^2\) (somme des \(n\) premiers entiers impairs).
Correction. On note \(P(n)\) : \(\displaystyle\sum_{k=1}^{n}(2k-1) = n^2\).
Initialisation. Pour \(n=1\) : \(2 \times 1 - 1 = 1 = 1^2\). \(P(1)\) vraie.
Hérédité. Soit \(n \geq 1\) fixé, on suppose \(P(n)\). Alors :
\(\displaystyle\sum_{k=1}^{n+1}(2k-1) = n^2 + \big(2(n+1)-1\big) = n^2 + 2n + 1 = (n+1)^2\)
C’est \(P(n+1)\).
Conclusion. D’après le principe de récurrence, \(P(n)\) est vraie pour tout \(n \geq 1\). ∎
Exercice 2 (★★). Soit \((u_n)\) la suite définie par \(u_0 = 2\) et \(u_{n+1} = 3u_n - 1\). Démontrer que pour tout \(n \geq 0\), \(u_n\) > \(0\). (Exercice de raisonnement : la formule explicite n’est pas donnée.)
Correction. On note \(P(n)\) : \(u_n\) > \(0\).
Initialisation. \(u_0 = 2\) > \(0\). \(P(0)\) vraie.
Hérédité. Soit \(n \geq 0\) fixé, on suppose \(u_n\) > \(0\). Comme \(u_n\) > \(0\), on a \(3u_n\) > \(0\). Il faut montrer \(3u_n - 1\) > \(0\). Une simple positivité ne suffit pas : renforçons l’hypothèse. On montre en fait \(u_n \geq 2\). Alors \(u_{n+1} = 3u_n - 1 \geq 3 \times 2 - 1 = 5 \geq 2\). Donc \(u_{n+1} \geq 2\) > \(0\).
Conclusion. Par récurrence, \(u_n \geq 2\) > \(0\) pour tout \(n \geq 0\). ∎
Leçon : quand l’hypothèse trop faible ne « passe » pas, il faut parfois démontrer une propriété plus forte. C’est une astuce clé pour l’étude des suites définies par récurrence.
Exercice 3 (★★). Démontrer que pour tout entier \(n \geq 0\), \(7^n - 1\) est divisible par \(6\).
Correction. On note \(P(n)\) : il existe \(k \in \mathbb{N}\) tel que \(7^n - 1 = 6k\).
Initialisation. \(7^0 - 1 = 0 = 6 \times 0\). \(P(0)\) vraie.
Hérédité. Soit \(n \geq 0\) fixé, on suppose \(7^n = 6k+1\). Alors :
\(7^{n+1} - 1 = 7(6k+1) - 1 = 42k + 6 = 6(7k+1)\)
\(7k+1\) est entier, donc \(P(n+1)\) est vraie.
Conclusion. Par récurrence, \(7^n - 1\) est divisible par \(6\) pour tout \(n \geq 0\). ∎
Pour un entraînement complet (sommes, inégalités, divisibilité, suites), va voir les exercices corrigés de récurrence en Terminale.
VII. Rédiger une récurrence en prépa 🔴 Prépa / Concours
En classe préparatoire, la trame reste identique, mais le correcteur attend un formalisme plus strict. Voici les exigences supplémentaires qui font la différence en colle et aux concours.
Ce que le correcteur attend :
- Quantificateurs explicites. Écris \(\forall n \in \mathbb{N},\ P(n)\) et non « pour tout \(n\) » vaguement placé. L’hypothèse de récurrence porte sur un \(n\) fixé : « Soit \(n \in \mathbb{N}\). Supposons \(P(n)\). »
- Distinction claire entre \(P(n)\) et sa valeur de vérité. Ne confonds pas la propriété (un prédicat) avec l’égalité qu’elle affirme.
- Choix de la bonne variante. Si le rang \(n+1\) dépend de plusieurs rangs précédents, annonce explicitement une récurrence forte ou double et adapte l’hypothèse : « Supposons \(P(k)\) vraie pour tout \(k\) tel que \(n_0 \leq k \leq n\). »
- Conclusion rigoureuse. « Par le principe de récurrence, \(\forall n \in \mathbb{N},\ P(n)\). »
Cette exigence se retrouve dans les preuves classiques de prépa : puissances de matrices, inégalité de Bernoulli, ou encore les suites récurrentes. Pour les récurrences linéaires du type \(u_{n+2} = au_{n+1} + bu_n\), la méthode se combine avec l’équation caractéristique des suites d’ordre 2.
Piège de prépa : dans une récurrence forte, oublier de vérifier assez de cas initiaux. Une récurrence double exige deux initialisations (\(P(n_0)\) et \(P(n_0+1)\)), sinon l’hérédité ne « démarre » pas.
VIII. Questions fréquentes
Comment rédiger une récurrence étape par étape ?
On suit quatre temps : (0) définir la propriété \(P(n)\), (1) l’initialisation (vérifier \(P(n_0)\)), (2) l’hérédité (supposer \(P(n)\) et démontrer \(P(n+1)\)), (3) la conclusion (invoquer le principe de récurrence). Chaque étape doit apparaître explicitement sur la copie, dans cet ordre.
Quelles sont les étapes d'un raisonnement par récurrence ?
Les trois étapes officielles sont l’initialisation, l’hérédité et la conclusion. On ajoute une étape 0 de bon sens : énoncer clairement la propriété \(P(n)\) que l’on veut démontrer avant de commencer.
Quelle est la différence entre l'initialisation et l'hérédité ?
L’initialisation vérifie que la propriété est vraie au premier rang (un cas concret, \(n_0\)). L’hérédité est un raisonnement général : elle prouve que si la propriété est vraie à un rang \(n\), alors elle l’est au rang \(n+1\). L’une constate, l’autre propage. Les deux sont indispensables.
Peut-on initialiser une récurrence à un autre rang que 0 ?
Oui. On initialise au premier rang \(n_0\) pour lequel la propriété est censée être vraie : ce peut être \(n_0 = 1\), \(n_0 = 2\) ou plus. La conclusion porte alors sur tous les entiers \(n \geq n_0\).
Quelle est la différence entre récurrence simple et récurrence forte ?
Dans une récurrence simple, l’hypothèse suppose \(P(n)\) vraie au seul rang \(n\). Dans une récurrence forte, on suppose \(P(k)\) vraie pour tous les rangs \(k\) de \(n_0\) à \(n\). On l’utilise quand le rang \(n+1\) dépend de plusieurs termes précédents. Détails et exemples sur la page récurrence forte et double.
IX. Pour aller plus loin
Tu maîtrises maintenant la rédaction d’une récurrence. Pour consolider :
- le raisonnement par récurrence — le cours complet : principe, variantes et histoire.
- Récurrence : exercices corrigés de Terminale — pour t’entraîner sur tous les types (sommes, inégalités, divisibilité).
- Récurrence forte et double — les variantes indispensables (Fibonacci, suites complexes).
- Suites définies par récurrence — appliquer la récurrence à l’étude des suites.
- La récurrence sert aussi à démontrer la formule d’une suite arithmétique ou géométrique.
Tu veux progresser plus vite et gagner en rigueur de rédaction ? Découvre les cours particuliers Excellence Maths, du lycée à la prépa.
