Raisonnement par récurrence : méthode et exercices corrigés

Le raisonnement par récurrence est la technique pour prouver qu'une propriété est vraie pour une infinité d'entiers d'un seul coup. Une formule de somme, une inégalité, une divisibilité, le terme général d'une suite : dès que ça dépend d'un entier $n$ et que tu ne peux pas vérifier « à la main » tous les cas, la récurrence est ton outil.

Cet article te donne tout : le principe (pourquoi ça marche, l'image des dominos), la rédaction type en 3 étapes que tu dois reproduire sans jamais improviser, le rôle central de l'hérédité, les pièges qui coûtent des points au bac et en khôlle, un aperçu de la récurrence double et forte pour la prépa, et 4 exercices corrigés du lycée à la Sup. Nos profs Hadamard, anciens MPSI/PCSI passés par l'X, l'ENS et CentraleSupélec, voient revenir les mêmes maladresses de rédaction chaque année, on les liste pour que tu les évites d'entrée.

Le principe : l'axiome de récurrence

On dispose d'une propriété $P(n)$ qui dépend d'un entier $n$, et d'un rang de départ $n_0$ (souvent $0$ ou $1$). Le principe de récurrence affirme :

En clair : si la propriété est vraie au premier rang, et si « vraie au rang $n$ » entraîne toujours « vraie au rang $n+1$ », alors elle est vraie à tous les rangs à partir de $n_0$. Ce n'est pas un théorème qu'on démontre en Terminale : c'est un axiome, une propriété fondamentale des entiers naturels, admise.

Cette image explique pourquoi les deux étapes sont indissociables. Un premier domino poussé mais pas d'enchaînement : rien ne tombe après. Un enchaînement parfait mais personne pour pousser le premier : rien ne tombe du tout. Garde cette image en tête, elle t'évitera l'erreur numéro un.

La rédaction type en 3 étapes

Une récurrence bien rédigée suit toujours le même squelette. Les correcteurs attendent ces trois étapes explicitement nommées. Ne les saute jamais, même quand la propriété te paraît évidente.

Les trois étapes, dans l'ordre :

Trois étapes, trois paragraphes. La phrase de l'étape 2, « Soit $n \geq n_0$ tel que $P(n)$ soit vraie », s'appelle l'hypothèse de récurrence. C'est ta munition : tu as le droit de t'en servir, et de rien d'autre.

L'hérédité, le cœur du raisonnement

L'hérédité est l'étape où tout se joue. On y démontre l'implication $P(n) \Rightarrow P(n+1)$. Concrètement, on suppose $P(n)$ vraie (l'hypothèse de récurrence), et on doit fabriquer $P(n+1)$ à partir de là.

La technique universelle : écris ce que tu veux prouver ($P(n+1)$), puis fais apparaître le rang $n$ pour brancher l'hypothèse de récurrence. Le pont entre le rang $n$ et le rang $n+1$ est presque toujours le même geste :

• Somme : on isole le dernier terme. $\displaystyle\sum_{k=0}^{n+1} = \left(\sum_{k=0}^{n}\right) + (\text{terme } n+1)$, et le paquet de gauche se remplace par l'hypothèse.
• Suite récurrente $u_{n+1} = f(u_n)$ : on applique $f$ à l'encadrement ou à l'égalité donnée par $P(n)$.
• Puissance : on factorise. $a^{n+1} = a \cdot a^{n}$, et $a^n$ se contrôle par l'hypothèse.
• Divisibilité : on écrit l'hypothèse sous forme $A_n = d \cdot k$, puis on exprime $A_{n+1}$ en fonction de $A_n$.

Si tu n'arrives pas à faire apparaître le rang $n$ dans ton expression de $P(n+1)$, c'est le signal que tu n'utilises pas ton hypothèse. Une hérédité qui ne mobilise jamais l'hypothèse de récurrence est fausse : tu as prouvé $P(n+1)$ tout seul, donc soit c'est une récurrence inutile, soit tu t'es trompé quelque part.

L'exemple pivot : la somme des entiers

Démontrons la formule reine, celle que tu retrouveras partout : pour tout entier $n \geq 1$,

Définition de la propriété. Pour $n \geq 1$, notons $P(n)$ la propriété : $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.

Étape 1, Initialisation. Pour $n = 1$ : le membre de gauche vaut $1$, le membre de droite vaut $\frac{1 \times 2}{2} = 1$. Les deux coïncident, donc $P(1)$ est vraie.

Étape 2, Hérédité. Soit $n \geq 1$ tel que $P(n)$ soit vraie. On suppose donc $\displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$. Montrons $P(n+1)$, c'est-à-dire $\displaystyle\sum_{k=1}^{n+1} k = \frac{(n+1)(n+2)}{2}$. On isole le dernier terme :

On met au même dénominateur et on factorise par $(n+1)$ :

C'est exactement $P(n+1)$. L'hérédité est établie.

Étape 3, Conclusion. $P(1)$ est vraie et $P$ est héréditaire, donc par le principe de récurrence, $P(n)$ est vraie pour tout $n \geq 1$.

Récurrence double et récurrence forte · cap prépa

La récurrence simple suffit au lycée dans l'immense majorité des cas. En prépa (MPSI, PCSI, MP2I), deux variantes deviennent incontournables dès qu'une suite dépend de plusieurs termes précédents.

Récurrence double

Quand $u_{n+2}$ se calcule à partir de $u_{n+1}$ et $u_n$ (relation d'ordre 2), un seul maillon ne suffit pas. On initialise deux rangs ($P(n_0)$ et $P(n_0+1)$), et l'hérédité suppose $P(n)$ et $P(n+1)$ pour en déduire $P(n+2)$.

Récurrence forte

Ici l'hypothèse est plus riche : on suppose $P(k)$ vraie pour tous les rangs $k$ de $n_0$ à $n$, et on en déduit $P(n+1)$. Utile quand le passage au rang suivant a besoin d'un rang antérieur quelconque, pas seulement du précédent (existence d'un diviseur premier, décomposition en produit de facteurs premiers…).

Ces variantes sont un classique de la première semaine de Sup. Elles figurent dans notre panorama du programme de maths en MPSI, où la récurrence structure tout le chapitre sur les suites et l'arithmétique.

5 erreurs classiques à éviter

Sur les copies de bac, de DS et de khôlles, ce sont toujours les mêmes fautes qui coûtent des points. Nos profs Hadamard, anciens taupins passés par l'X et CentraleSupélec, les traquent dès les premières rédactions de leurs élèves.

1. Oublier l'initialisation. L'erreur reine. Une propriété peut être héréditaire et fausse partout (voir l'exercice 4). Sans le premier domino, tu n'as rien prouvé, quelle que soit la beauté de ton hérédité.
2. Confondre hypothèse et conclusion. Écrire « supposons $P(n+1)$ » au lieu de « supposons $P(n)$, montrons $P(n+1)$ ». On suppose le rang $n$, on démontre le rang $n+1$. Jamais l'inverse.
3. Ne pas utiliser l'hypothèse de récurrence. Si ton calcul d'hérédité ne branche jamais $P(n)$, c'est un signal d'alarme : soit la récurrence est inutile, soit tu t'es trompé de méthode. L'hypothèse doit servir.
4. Oublier de définir $P(n)$. Se lancer dans les calculs sans avoir écrit « notons $P(n)$ la propriété… ». Le correcteur ne sait plus ce que tu inities ni ce que tu supposes. Toujours nommer la propriété d'abord.
5. Initialiser au mauvais rang. Une inégalité vraie seulement à partir de $n = 4$ ne s'initialise pas à $n = 0$. Repère le vrai rang de départ $n_0$ avant de rédiger, sinon l'initialisation échoue et tout s'effondre.

4 exercices corrigés · Terminale → MPSI

Exercice 1, Somme des carrés · niveau Terminale

Énoncé. Montrer que pour tout $n \geq 1$, $\displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$.

Solution. Notons $P(n)$ cette égalité. Initialisation : pour $n=1$, à gauche $1$, à droite $\frac{1 \cdot 2 \cdot 3}{6} = 1$. $P(1)$ vraie. Hérédité : soit $n \geq 1$ tel que $P(n)$ soit vraie. On isole le dernier terme :

On factorise par $(n+1)$ au numérateur : $(n+1)\bigl[n(2n+1) + 6(n+1)\bigr] = (n+1)(2n^2 + 7n + 6) = (n+1)(n+2)(2n+3)$. D'où :

ce qui est $P(n+1)$. Conclusion : par récurrence, $P(n)$ est vraie pour tout $n \geq 1$.

Exercice 2, Inégalité · niveau Terminale, initialisation décalée

Énoncé. Montrer que pour tout entier $n \geq 4$, $2^n \geq n^2$.

Solution. Notons $P(n)$ : $2^n \geq n^2$. Initialisation au rang 4 (et pas 0 : l'inégalité est fausse pour $n = 3$, où $8 < 9$) : pour $n = 4$, $2^4 = 16$ et $4^2 = 16$, donc $16 \geq 16$, $P(4)$ vraie. Hérédité : soit $n \geq 4$ tel que $2^n \geq n^2$. Alors :

Il reste à montrer $2n^2 \geq (n+1)^2$, soit $2n^2 \geq n^2 + 2n + 1$, c'est-à-dire $n^2 - 2n - 1 \geq 0$. Pour $n \geq 4$, $n^2 - 2n - 1 = n(n-2) - 1 \geq 4 \times 2 - 1 = 7 > 0$. Donc $2^{n+1} \geq 2n^2 \geq (n+1)^2$, ce qui est $P(n+1)$.

Conclusion : par récurrence, $2^n \geq n^2$ pour tout $n \geq 4$. Retiens l'idée : le rang de départ n'est pas toujours $0$, on cale l'initialisation là où la propriété commence à être vraie.

Exercice 3, Divisibilité · niveau Terminale / MPSI

Énoncé. Montrer que pour tout $n \geq 0$, $4^n - 1$ est divisible par $3$.

Solution. Notons $P(n)$ : « $3$ divise $4^n - 1$ ». Initialisation : pour $n = 0$, $4^0 - 1 = 0 = 3 \times 0$, divisible par $3$. $P(0)$ vraie. Hérédité : soit $n \geq 0$ tel que $P(n)$ soit vraie, c'est-à-dire $4^n - 1 = 3k$ pour un certain entier $k$, donc $4^n = 3k + 1$. Alors :

Comme $4k + 1$ est entier, $3$ divise $4^{n+1} - 1$ : $P(n+1)$ est vraie. Conclusion : par récurrence, $3$ divise $4^n - 1$ pour tout $n \geq 0$. Le geste clé : écrire l'hypothèse sous la forme $4^n = 3k + 1$ pour faire entrer le rang $n$ dans le calcul du rang $n+1$.

Exercice 4, Le contre-exemple qui prouve l'utilité de l'initialisation

Énoncé. On considère la propriété $Q(n)$ : « $3$ divise $4^n + 1$ ». Montrer que $Q$ est héréditaire, puis qu'elle est pourtant fausse pour tout $n$. Que conclure ?

Solution. Hérédité : supposons $Q(n)$, soit $4^n + 1 = 3k$, donc $4^n = 3k - 1$. Alors :

Donc $Q(n) \Rightarrow Q(n+1)$ : la propriété est bien héréditaire. Pourtant elle est fausse partout : $4 \equiv 1 \ [3]$, donc $4^n \equiv 1 \ [3]$, d'où $4^n + 1 \equiv 2 \ [3]$, jamais divisible par $3$. Aucune valeur de $n$ ne vérifie $Q(n)$.

Ce qu'il faut retenir

• Le principe : initialisation + hérédité $\Rightarrow$ propriété vraie pour tout $n \geq n_0$. L'image des dominos, indissociable.
• Les 3 étapes : définir $P(n)$, initialiser au bon rang, prouver l'hérédité $P(n) \Rightarrow P(n+1)$, conclure.
• L'hérédité : on suppose $P(n)$ (hypothèse de récurrence), on écrit le but $P(n+1)$, on fait apparaître le rang $n$ pour brancher l'hypothèse.
• Les variantes prépa : récurrence double (deux initialisations, hypothèse sur $n$ et $n+1$), récurrence forte (hypothèse de $n_0$ à $n$).
• Les pièges : initialisation oubliée ou mal calée, hypothèse et conclusion inversées, hypothèse jamais utilisée, $P(n)$ non défini.
• La preuve par l'absurde de l'utilité : « $4^n+1$ divisible par $3$ » est héréditaire mais fausse partout. Sans initialisation, rien n'est prouvé.

La récurrence n'est pas qu'un exercice de Terminale : c'est le réflexe de démonstration sur les entiers, que tu réutiliseras sans arrêt en prépa pour les suites, l'arithmétique, les matrices ou l'analyse. La maîtriser proprement dès le lycée, c'est se donner une base solide pour tout le reste. Elle va d'ailleurs de pair avec le travail d'apprentissage des démonstrations du cours par cœur, où la rédaction rigoureuse fait la différence.

Pour t'entraîner, applique la méthode aux formules classiques des suites arithmétiques et géométriques, terrain de jeu naturel de la récurrence, et resitue-la dans le programme de spécialité maths de Terminale.