Raisonnement par récurrence : méthode + exemple détaillé

Quand utiliser la récurrence ?

La récurrence sert à démontrer une propriété P(n) vraie pour tout entier $n\ge n_0$ (souvent $n_0=0$ ou $1$). Tu reconnais le besoin de récurrence quand l'énoncé dit : « démontrer par récurrence que… ».

Les 3 étapes obligatoires

1. Initialisation : on vérifie que $P(n_0)$ est vraie (cas de base).
2. Hérédité : on suppose $P(n)$ vraie pour un certain $n\ge n_0$, 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

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

Notation. On note $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$. 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{ par HR}}{\underbrace{\sum _{k=1}^{n}k}}+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}$

C'est bien la formule pour $n+1$. Donc $P(n+1)$ est vraie.

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

Les 2 pièges classiques

• Oublier l'initialisation : sans cas de base, la chaîne ne démarre pas. C'est une faute lourde (jusqu'à 50 % des points perdus).
• Mal poser l'hypothèse : tu supposes $P(n)$, pas $P(n+1)$. L'hypothèse de récurrence (HR) est la prémisse, pas la conclusion.

Variantes utiles

• Récurrence forte : on suppose $P(n_0),P(n_0+1),\dots ,P(n)$ toutes vraies pour déduire $P(n+1)$. Utile quand $u_{n+1}$ dépend de plusieurs termes précédents.
• Récurrence double : vérifier $P(n_0)$ et $P(n_0+1)$, puis montrer que $P(n)$ et $P(n+1)$ impliquent $P(n+2)$ (suites de type $u_{n+2}=a{u}_{n+1}+b{u}_n$).

Pour aller plus loin

Entraîne-toi sur les exercices de suites du 2BAC — la moitié des questions de bac sur les suites se résolvent par récurrence.