Raisonnement par récurrence

Les prérequis à avoir en tête

Avant de te lancer, trois choses suffisent :

• Comprendre qu'une propriété $P(n)$ est une phrase mathématique qui dépend d'un entier $n$ (par exemple « $2^n \ge n+1$ » ou « la somme $1+2+\dots+n$ vaut $\frac{n(n+1)}{2}$ »). Selon la valeur de $n$, elle est vraie ou fausse.
• Savoir manipuler et factoriser une expression algébrique : mettre un facteur en commun, réduire au même dénominateur.
• Repérer le rang de départ $n_0$ : c'est le premier entier pour lequel on veut prouver la propriété (souvent $0$ ou $1$).

Le symbole $\sum_{k=1}^{n} k$ se lit simplement « la somme $1+2+\dots+n$ » : ne te laisse pas impressionner par la notation.

L'idée en une image : les dominos

Imagine une longue file de dominos. Tu veux être sûr qu'ils tombent tous. Il te suffit de vérifier deux choses :

• le premier tombe : c'est l'initialisation ;
• chaque domino qui tombe fait tomber le suivant : c'est l'hérédité.

Si ces deux points sont vrais, alors de proche en proche, tous les dominos tombent. C'est exactement ça, une récurrence. La recette tient en trois lignes :

1. Initialisation : je vérifie que $P(n_0)$ est vraie (un simple calcul).

2. Hérédité : je suppose $P(n)$ vraie pour un $n \ge n_0$ quelconque (c'est l'hypothèse de récurrence), et je montre qu'alors $P(n+1)$ est vraie.

3. Conclusion : j'écris « par le principe de récurrence, $P(n)$ est vraie pour tout $n \ge n_0$ ».

Un exemple traité en entier

But : montrer que pour tout $n \ge 1$, $1+2+\dots+n = \frac{n(n+1)}{2}$. On note $P(n)$ cette égalité.

Initialisation ($n=1$). À gauche : $1$. À droite : $\frac{1 \times 2}{2} = 1$. Les deux côtés sont égaux, donc $P(1)$ est vraie.

Hérédité. Soit $n \ge 1$ fixé. On suppose $P(n)$ vraie, c'est-à-dire $1+2+\dots+n = \frac{n(n+1)}{2}$.

On regarde la somme au rang suivant :

$1+2+\dots+n+(n+1) = \big(1+2+\dots+n\big) + (n+1)$

$= \frac{n(n+1)}{2} + (n+1)$   (on a remplacé grâce à l'hypothèse de récurrence)

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

C'est bien la formule attendue au rang $n+1$ (remplace $n$ par $n+1$ dans $\frac{n(n+1)}{2}$ pour vérifier). Donc $P(n+1)$ est vraie.

Conclusion. $P(1)$ est vraie et $P(n) \Rightarrow P(n+1)$ : par récurrence, $1+2+\dots+n = \frac{n(n+1)}{2}$ pour tout $n \ge 1$.

Le vocabulaire, proprement

Propriété $P(n)$. C'est un énoncé dépendant de l'entier $n$, qui peut être vrai ou faux selon $n$. Démontrer « par récurrence » une propriété, c'est prouver qu'elle est vraie pour tous les entiers $n$ à partir d'un rang $n_0$.

Rang initial $n_0$. C'est le premier entier concerné. Souvent $n_0 = 0$ ou $n_0 = 1$, mais ce peut être n'importe quel entier (par exemple $n_0 = 4$ si la propriété ne devient vraie qu'à partir de $4$).

Hypothèse de récurrence. C'est la phrase « on suppose $P(n)$ vraie pour un entier $n \ge n_0$ fixé ». Attention : on suppose $P(n)$ pour un rang $n$, pas pour tous ; sinon on supposerait déjà ce que l'on cherche à démontrer.

Le principe de récurrence et la méthode

Le principe de récurrence s'énonce ainsi. Si :

• $P(n_0)$ est vraie (initialisation), et
• pour tout entier $n \ge n_0$, l'implication $P(n) \Rightarrow P(n+1)$ est vraie (hérédité),

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

La rédaction se fait toujours en trois étapes :

1. Initialisation. On énonce $P(n_0)$ et on la vérifie par un calcul explicite (on calcule les deux membres et on constate l'égalité, ou on vérifie l'inégalité).

2. Hérédité. On écrit « soit $n \ge n_0$ un entier fixé ; supposons $P(n)$ vraie ». On énonce clairement ce que dit $P(n)$, puis on démontre $P(n+1)$ en se servant de l'hypothèse de récurrence : c'est le cœur du raisonnement.

3. Conclusion. On rappelle que l'initialisation et l'hérédité sont établies, et on conclut : « par le principe de récurrence, $P(n)$ est vraie pour tout $n \ge n_0$ ».

Vu autrement, la récurrence enchaîne les implications $P(n_0) \Rightarrow P(n_0+1) \Rightarrow P(n_0+2) \Rightarrow \dots$, et l'initialisation « allume » toute la chaîne.

Exemple traité : une divisibilité

But : montrer que pour tout $n \ge 0$, $4^{n} - 1$ est divisible par $3$. On note $P(n)$ : « $4^{n}-1$ est un multiple de $3$ ».

Initialisation ($n=0$). $4^{0} - 1 = 1 - 1 = 0$, et $0 = 3 \times 0$ est bien un multiple de $3$. Donc $P(0)$ est vraie.

Hérédité. Soit $n \ge 0$ fixé. Supposons $P(n)$ : il existe un entier $k$ tel que $4^{n} - 1 = 3k$, c'est-à-dire $4^{n} = 3k + 1$.

Alors : $4^{n+1} - 1 = 4 \times 4^{n} - 1 = 4(3k+1) - 1 = 12k + 4 - 1 = 12k + 3 = 3(4k+1)$.

Comme $4k+1$ est un entier, $4^{n+1} - 1$ est un multiple de $3$ : $P(n+1)$ est vraie.

Conclusion. Par récurrence, $4^{n}-1$ est divisible par $3$ pour tout $n \ge 0$.

Ensemble : une inégalité

But : montrer que pour tout $n \ge 0$, $2^{n} \ge n+1$. On note $P(n)$ cette inégalité.

On commence toujours par l'initialisation.

Initialisation ($n=0$). $2^{0} = 1$ et $0 + 1 = 1$. On a $1 \ge 1$ : vrai. Donc $P(0)$ est vraie. (Ici c'est une égalité, et le symbole $\ge$ l'autorise.)

Puis l'hérédité : on fixe un rang et on suppose la propriété à ce rang.

Hérédité. Soit $n \ge 0$ fixé. Supposons $P(n)$ : $2^{n} \ge n+1$. On veut obtenir $2^{n+1} \ge (n+1)+1 = n+2$.

On part du terme à faire grandir : $2^{n+1} = 2 \times 2^{n}$.

Grâce à l'hypothèse $2^{n} \ge n+1$, en multipliant par $2 \gt 0$ : $2 \times 2^{n} \ge 2(n+1) = 2n+2$.

Or $2n + 2 = (n+2) + n \ge n+2$ car $n \ge 0$. (On a simplement laissé tomber le terme positif $n$.)

En rassemblant : $2^{n+1} \ge n+2$, c'est-à-dire $P(n+1)$.

Conclusion. Par récurrence, $2^{n} \ge n+1$ pour tout $n \ge 0$.

Ensemble : une divisibilité

But : montrer que pour tout $n \ge 0$, $7^{n} - 1$ est divisible par $6$. On note $P(n)$ : « $7^{n} - 1$ est un multiple de $6$ ».

Initialisation ($n=0$). $7^{0} - 1 = 0 = 6 \times 0$ : multiple de $6$. $P(0)$ est vraie. (Au rang $0$ on tombe souvent sur $0$, qui est multiple de tout : pratique.)

Hérédité. Soit $n \ge 0$ fixé. Supposons $P(n)$ : il existe un entier $k$ avec $7^{n} - 1 = 6k$, donc $7^{n} = 6k + 1$.

On calcule le rang suivant en faisant apparaître $7^{n}$ : $7^{n+1} - 1 = 7 \times 7^{n} - 1$.

On remplace $7^{n}$ par $6k+1$ ; c'est l'étape clé, celle qui utilise l'hypothèse : $= 7(6k+1) - 1 = 42k + 7 - 1 = 42k + 6$.

On factorise par $6$ : $42k + 6 = 6(7k + 1)$. Comme $7k+1$ est entier, c'est un multiple de $6$ : $P(n+1)$ est vraie.

Conclusion. Par récurrence, $7^{n} - 1$ est divisible par $6$ pour tout $n \ge 0$.

Ensemble : une somme

But : montrer que la somme des $n$ premiers entiers impairs vaut $n^{2}$, autrement dit pour tout $n \ge 1$ : $1 + 3 + 5 + \dots + (2n-1) = n^{2}$. On note $P(n)$ cette égalité.

Initialisation ($n=1$). À gauche, le premier impair : $2 \times 1 - 1 = 1$. À droite : $1^{2} = 1$. Égalité, donc $P(1)$ est vraie.

Hérédité. Soit $n \ge 1$ fixé. Supposons $P(n)$ : $1 + 3 + \dots + (2n-1) = n^{2}$.

Le terme suivant à ajouter est le $(n+1)$-ième nombre impair, soit $2(n+1) - 1 = 2n+1$. On écrit alors :

$1 + 3 + \dots + (2n-1) + (2n+1) = \underbrace{\big(1+3+\dots+(2n-1)\big)}_{=\,n^{2}\ \text{par hypothèse}} + (2n+1)$

$= n^{2} + 2n + 1 = (n+1)^{2}$.

C'est exactement la formule au rang $n+1$ : $P(n+1)$ est vraie.

Conclusion. Par récurrence, $1 + 3 + \dots + (2n-1) = n^{2}$ pour tout $n \ge 1$.

Ce que le correcteur attend (et les pièges)

Une récurrence bien notée respecte quelques réflexes de rédaction :

• Fixe le rang. Écris « soit $n \ge n_0$ un entier fixé » au début de l'hérédité. On raisonne à $n$ figé, pas sur tous les $n$ à la fois.
• Énonce l'hypothèse de récurrence. Recopie ce que dit $P(n)$ ; le correcteur veut lire la phrase « supposons $P(n)$ vraie, c'est-à-dire … ».
• Sers-toi vraiment de l'hypothèse. Le moment où tu remplaces grâce à $P(n)$ doit être visible. Une hérédité qui n'utilise pas l'hypothèse est fausse (ou inutile).
• Conclus dans les règles. « L'initialisation et l'hérédité sont vérifiées, donc par le principe de récurrence… ». Ne saute jamais la conclusion.

Le piège n°1 : oublier l'initialisation. Ce n'est pas un détail. Prends $P(n)$ : « $10^{n} + 1$ est divisible par $3$ ».

Hérédité : supposons $10^{n} + 1 = 3k$, donc $10^{n} = 3k - 1$. Alors $10^{n+1} + 1 = 10 \times 10^{n} + 1 = 10(3k-1) + 1 = 30k - 9 = 3(10k - 3)$ : multiple de $3$. L'hérédité fonctionne !

Pourtant $P(0)$ : $10^{0} + 1 = 2$ n'est pas divisible par $3$, et en réalité aucun $P(n)$ n'est vrai. Moralité : sans initialisation, l'hérédité seule ne prouve rien. Le premier domino doit tomber.

Autres pièges classiques : le raisonnement circulaire (utiliser la conclusion cherchée comme si elle était déjà acquise), et confondre « on suppose $P(n)$ pour un $n$ » avec « on suppose $P(n)$ pour tout $n$ » (là, tu supposerais déjà le résultat).

Problème type : l'inégalité de Bernoulli

Énoncé. Soit $a$ un réel avec $a \ge -1$. Montrer que pour tout entier $n \ge 0$ : $(1+a)^{n} \ge 1 + na$. On note $P(n)$ cette inégalité.

Initialisation ($n=0$). $(1+a)^{0} = 1$ et $1 + 0 \times a = 1$. On a $1 \ge 1$ : $P(0)$ est vraie.

Hérédité. Soit $n \ge 0$ fixé. Supposons $P(n)$ : $(1+a)^{n} \ge 1 + na$.

On veut minorer $(1+a)^{n+1} = (1+a)^{n} \times (1+a)$.

Point délicat : pour multiplier l'inégalité par $(1+a)$ sans en changer le sens, il faut $1 + a \ge 0$, ce qui est vrai puisque $a \ge -1$. On peut donc écrire :

$(1+a)^{n+1} = (1+a)^{n}(1+a) \ge (1 + na)(1 + a)$.

On développe le membre de droite : $(1+na)(1+a) = 1 + a + na + na^{2} = 1 + (n+1)a + na^{2}$.

Comme $na^{2} \ge 0$, on a $1 + (n+1)a + na^{2} \ge 1 + (n+1)a$. Par transitivité :

$(1+a)^{n+1} \ge 1 + (n+1)a$, ce qui est exactement $P(n+1)$.

Conclusion. Par récurrence, $(1+a)^{n} \ge 1 + na$ pour tout $n \ge 0$ (et tout réel $a \ge -1$). Ce que le correcteur guette ici : la justification du signe de $1+a$ avant de multiplier l'inégalité.

Problème type : une suite majorée

Énoncé. On définit la suite $(u_n)$ par $u_0 = 1$ et, pour tout $n \ge 0$, $u_{n+1} = \frac{1}{3}u_n + 2$. Montrer que pour tout $n \ge 0$, $u_n \le 3$. On note $P(n)$ : « $u_n \le 3$ ».

Initialisation ($n=0$). $u_0 = 1 \le 3$ : $P(0)$ est vraie.

Hérédité. Soit $n \ge 0$ fixé. Supposons $P(n)$ : $u_n \le 3$.

On exprime $u_{n+1}$ à partir de $u_n$ : $u_{n+1} = \frac{1}{3}u_n + 2$.

Comme $u_n \le 3$ et que $\frac{1}{3} \gt 0$, on peut multiplier l'inégalité : $\frac{1}{3}u_n \le \frac{1}{3} \times 3 = 1$.

On ajoute $2$ aux deux membres : $\frac{1}{3}u_n + 2 \le 1 + 2 = 3$, c'est-à-dire $u_{n+1} \le 3$. Donc $P(n+1)$ est vraie.

Conclusion. Par récurrence, $u_n \le 3$ pour tout $n \ge 0$ : la suite est majorée par $3$. C'est souvent la première étape d'un exercice de suites : prouver une majoration (ou une minoration) par récurrence, avant d'étudier la monotonie et la convergence.

Pourquoi la récurrence est-elle valide ?

On l'utilise comme une recette, mais d'où vient sa légitimité ? Elle repose sur une propriété fondamentale de $\mathbb{N}$ : toute partie non vide de $\mathbb{N}$ possède un plus petit élément (on dit que $\mathbb{N}$ est bien ordonné).

Idée de justification, par l'absurde. Supposons l'initialisation et l'hérédité vraies, mais imaginons que $P(n)$ soit fausse pour au moins un entier. L'ensemble $E$ des entiers $n \ge n_0$ où $P(n)$ est fausse serait alors non vide ; il aurait donc un plus petit élément $m$.

Ce $m$ ne peut pas valoir $n_0$ (car $P(n_0)$ est vraie par l'initialisation), donc $m \gt n_0$ et $m - 1 \ge n_0$. Comme $m$ est le plus petit rang « fautif », $P(m-1)$ est vraie. Mais l'hérédité donne $P(m-1) \Rightarrow P(m)$, donc $P(m)$ serait vraie : contradiction avec $m \in E$.

Donc $E$ est vide : $P(n)$ est vraie pour tout $n \ge n_0$. Le principe de récurrence est en fait un axiome de la construction des entiers (les axiomes de Peano), équivalent au bon ordre de $\mathbb{N}$.

Les grandes sœurs : récurrence double et récurrence forte

La récurrence « simple » n'est qu'une version parmi d'autres. Deux variantes reviennent souvent :

La récurrence double. Quand $P(n+1)$ a besoin de deux rangs précédents, typiquement pour les suites définies par $u_{n+2} = a\,u_{n+1} + b\,u_n$. On initialise alors deux rangs, $P(n_0)$ et $P(n_0+1)$, et l'hérédité devient : $\big(P(n)\ \text{et}\ P(n+1)\big) \Rightarrow P(n+2)$.

La récurrence forte. Ici l'hérédité suppose $P(k)$ vraie pour tous les rangs $k$ de $n_0$ jusqu'à $n$, afin d'en déduire $P(n+1)$. C'est l'outil idéal quand le rang suivant dépend de plusieurs rangs antérieurs, voire de tous : par exemple pour prouver que tout entier supérieur ou égal à $2$ se décompose en produit de nombres premiers.

Dans les trois cas, l'esprit reste le même : une base solide plus un pas qui se propage. Seule change la « quantité de passé » dont on a besoin pour faire le pas suivant.

Où tu vas la recroiser

La récurrence n'est pas un chapitre isolé, c'est un outil transversal :

• Les suites. Pour montrer qu'une suite est majorée ou minorée, puis monotone, on enchaîne deux récurrences ; combinées au théorème de la limite monotone, elles donnent la convergence. C'est le combo le plus fréquent au bac.
• Le dénombrement et le binôme. La formule du binôme de Newton et plusieurs identités sur les coefficients binomiaux se démontrent par récurrence.
• Les définitions elles-mêmes. Une suite donnée par $u_{n+1} = f(u_n)$ est une définition par récurrence : la récurrence sert alors à construire, pas seulement à prouver.
• Après le bac. Tu la retrouveras partout (inégalités, algèbre linéaire, algorithmique), avec sa cousine la descente infinie, qui prouve qu'une chose est impossible en fabriquant une suite d'entiers strictement décroissante, ce qui ne peut pas exister.

Bref : maîtriser la récurrence, c'est débloquer une bonne partie du programme d'analyse de Terminale et poser les fondations de tes maths d'après.