Raisonnement par récurrence : méthode + exemples détaillés

Quand utiliser la récurrence ?

Le raisonnement par récurrence sert à démontrer qu'une propriété $P(n)$ est vraie pour tout entier $n\ge n_0$ (souvent $n_0=0$ ou $1$). C'est l'outil de démonstration le plus testé au bac, en particulier sur les suites. On y pense dès que l'énoncé contient « démontrer par récurrence que… » ou qu'une formule doit être prouvée pour tout $n$.

L'image classique : une rangée infinie de dominos. Si le premier tombe (initialisation) et si chaque domino fait tomber le suivant (hérédité), alors tous tombent (conclusion). C'est précisément ce que garantit l'axiome de récurrence : si une partie de $\mathbb{N}$ contient $n_0$ et est stable par passage de $n$ à $n+1$, alors elle contient tous les entiers $\ge n_0$. La récurrence n'est donc pas une astuce, mais une propriété fondamentale des entiers naturels.

Les 3 étapes obligatoires

1. Initialisation : on vérifie que $P(n_0)$ est vraie (le cas de base).
2. Hérédité : on suppose $P(n)$ vraie pour un certain $n\ge n_0$ (c'est l'hypothèse de récurrence, HR), et on démontre que $P(n+1)$ l'est aussi.
3. Conclusion : on rédige « D'après le principe de récurrence, $P(n)$ est vraie pour tout $n\ge n_0$. »

Exemple résolu — somme des premiers entiers

Énoncé. Démontrer que pour tout $n\in {\mathbb{N}}^{\ast }$ : $\sum _{k=1}^{n}k=\frac{n(n+1)}{2}$.

Notation. On pose $P(n)$ : « $\sum _{k=1}^{n}k=\frac{n(n+1)}{2}$ ».

Initialisation. Pour $n=1$ : à gauche $\sum _{k=1}^{1}k=1$ ; à droite $\frac{1\times 2}{2}=1$. Les deux coïncident, donc $P(1)$ est vraie.

Hérédité. Supposons $P(n)$ vraie pour un certain $n\ge 1$. Montrons $P(n+1)$ :

$\sum _{k=1}^{n+1}k=\underset{=\frac{n(n+1)}{2}\text{(HR)}}{\underbrace{\sum _{k=1}^{n}k}}+(n+1)=\frac{n(n+1)}{2}+(n+1)$.

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

$=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}$.

C'est exactement la formule au rang $n+1$ (avec $n+1$ à la place de $n$). Donc $P(n+1)$ est vraie.

Conclusion. Par récurrence, $P(n)$ est vraie pour tout $n\ge 1$.

Second exemple — une inégalité

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

Initialisation. Pour $n=4$ : $2^4=16$ et $4^2=16$, donc $16\ge 16$ : $P(4)$ est vraie. (Attention, l'initialisation démarre ici à $n_0=4$, pas à $0$ !)

Hérédité. Supposons $2^n\ge n^2$ pour un $n\ge 4$. Alors $2^{n+1}=2\cdot 2^n\ge 2n^2$. Or pour $n\ge 4$ on a $2n^2\ge (n+1{)}^2$ (car $2n^2-(n+1{)}^2=n^2-2n-1\ge 0$ dès $n\ge 3$). Donc $2^{n+1}\ge (n+1{)}^2$ : $P(n+1)$ est vraie.

Conclusion. Par récurrence, $2^n\ge n^2$ pour tout $n\ge 4$.

Les 2 pièges classiques

• Oublier l'initialisation. Sans cas de base, la chaîne de dominos ne démarre jamais : la démonstration est nulle. C'est une faute lourde, lourdement sanctionnée.
• Confondre hypothèse et conclusion. On suppose $P(n)$ (la prémisse), on prouve $P(n+1)$. Utiliser $P(n+1)$ comme acquis pour démontrer $P(n+1)$ est un raisonnement circulaire : zéro.

Un troisième écueil fréquent : commencer l'initialisation au mauvais rang. Si la propriété n'est vraie qu'à partir de $n_0=4$, initialiser à $n=0$ donne une initialisation fausse.

Un quatrième, plus subtil : ne pas réellement utiliser l'hypothèse de récurrence dans l'hérédité. Si ta démonstration de $P(n+1)$ ne fait jamais appel à $P(n)$, c'est que la récurrence était inutile — ou, plus souvent, que tu as commis une erreur. L'HR doit apparaître explicitement (on l'indique souvent par « par HR ») au moment décisif du calcul.

Exemple avec une suite — démontrer une majoration

Énoncé. Soit la suite définie par $u_0=0$ et $u_{n+1}=\sqrt{u_n+2}$. Démontrer que pour tout $n\in \mathbb{N}$, $0\le u_n\le 2$.

Notation. $P(n)$ : « $0\le u_n\le 2$ ».

Initialisation. $u_0=0$, donc $0\le u_0\le 2$ : $P(0)$ est vraie.

Hérédité. Supposons $0\le u_n\le 2$. Alors $2\le u_n+2\le 4$, et comme la fonction racine est croissante, $\sqrt{2}\le \sqrt{u_n+2}\le 2$, c'est-à-dire $\sqrt{2}\le u_{n+1}\le 2$. En particulier $0\le u_{n+1}\le 2$ : $P(n+1)$ est vraie.

Conclusion. Par récurrence, $0\le u_n\le 2$ pour tout $n\in \mathbb{N}$. Cette majoration est le premier pas vers l'étude de la convergence de la suite.

Variantes utiles

• Récurrence forte : on suppose $P(n_0),P(n_0+1),\dots ,P(n)$ toutes vraies pour en déduire $P(n+1)$. Indispensable quand $u_{n+1}$ dépend de plusieurs termes antérieurs.
• Récurrence double : on vérifie $P(n_0)$ et $P(n_0+1)$, puis on montre que $P(n)$ et $P(n+1)$ entraînent $P(n+2)$. Adaptée aux suites du type $u_{n+2}=a{u}_{n+1}+b{u}_n$.

À retenir

Trois étapes, jamais une de moins : initialisation (le premier domino), hérédité (chaque domino pousse le suivant, en partant de l'HR), conclusion. On suppose $P(n)$, on prouve $P(n+1)$ — jamais l'inverse — et on démarre l'initialisation au bon rang $n_0$.

Pour aller plus loin

Entraîne-toi sur les exercices de suites du Terminale : près de la moitié des questions de bac sur les suites se résolvent par récurrence.