Le raisonnement par récurrence

Imagine une file infinie de dominos. Si le premier tombe, et si chaque domino qui tombe renverse le suivant, alors tous les dominos tombent. Le raisonnement par récurrence, c’est exactement cette idée : un outil pour démontrer qu’une propriété $P(n)$ est vraie pour tous les entiers à partir d’un rang donné — sans avoir à les vérifier un par un. C’est la première grande nouveauté de la Terminale, et elle sert partout : suites, inégalités, divisibilité.

Le principe

Soit $P(n)$ une propriété qui dépend d’un entier naturel $n$, et $n_0$ un entier. Si :

• Initialisation : $P(n_0)$ est vraie — le premier domino tombe ;
• Hérédité : pour tout entier $n \geq n_0$, si $P(n)$ est vraie, alors $P(n+1)$ est vraie — chaque domino renverse le suivant ;

alors $P(n)$ est vraie pour tout entier $n \geq n_0$.

Les deux conditions sont indispensables : une hérédité sans initialisation ne démontre rien (des dominos bien alignés ne tombent pas tout seuls), et une initialisation sans hérédité non plus.

La rédaction type en trois étapes

Exemple rédigé : une somme classique

Montrons que pour tout entier $n \geq 1$ : $1 + 2 + \cdots + n = \dfrac{n(n+1)}{2}$.

• Initialisation ($n = 1$) : à gauche, la somme vaut $1$ ; à droite, $\dfrac{1 \times 2}{2} = 1$. La propriété est vraie au rang $1$.
• Hérédité : supposons la formule vraie pour un certain entier $n \geq 1$. Alors, en isolant le dernier terme :

$1 + 2 + \cdots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\left(\frac{n}{2} + 1\right) = \frac{(n+1)(n+2)}{2}$

C’est exactement la formule au rang $n+1$.

• Conclusion : par récurrence, la formule est vraie pour tout entier $n \geq 1$.

Le réflexe clé de l’hérédité d’une somme : isoler le dernier terme pour faire apparaître l’hypothèse de récurrence, puis factoriser.

L’inégalité de Bernoulli

Récurrence et suites : les trois missions classiques

Quand une suite est définie par récurrence ($u_{n+1}$ en fonction de $u_n$), impossible de calculer directement $u_{1000}$ : la récurrence est l’outil naturel pour établir ses propriétés.

• Majoration ou minoration : montrer que $u_n \leq M$ pour tout $n$. Dans l’hérédité, on part de $u_n \leq M$ et on suit les opérations qui fabriquent $u_{n+1}$. Exemple : si $u_{n+1} = \dfrac{1}{2}u_n + 3$ et $u_n \leq 6$, alors $u_{n+1} \leq \dfrac{1}{2} \times 6 + 3 = 6$ : la majoration se transmet.
• Monotonie : montrer par exemple que $u_{n+1} \geq u_n$ pour tout $n$ — souvent en s’appuyant sur une majoration démontrée juste avant, ou sur la croissance d’une fonction.
• Formule explicite : calculer les premiers termes, conjecturer une formule, puis la démontrer par récurrence. Exemple : $u_0 = 5$ et $u_{n+1} = 2u_n - 3$ donnent $5$, $7$, $11$, $19$… On conjecture $u_n = 2^{n+1} + 3$, et l’hérédité le confirme : $2\left(2^{n+1} + 3\right) - 3 = 2^{n+2} + 3$.

Ces trois missions se combinent : au chapitre suivant, « croissante et majorée » deviendra un argument de convergence.

Les pièges classiques