Terminale · Fiche méthode 3 sur 12 · Suites
Comment faire une démonstration par récurrence ?
Une récurrence se rédige en trois temps : initialisation (la propriété est vraie au premier rang), hérédité (si elle est vraie au rang $n$, alors elle l'est au rang $n+1$), conclusion (elle est donc vraie pour tout $n$).
La méthode en 5 étapes
1Énoncer la propriété P(n)
On écrit précisément « Pour tout entier $n\ge n_0$, soit $P(n)$ : … ». Une propriété mal définie rend toute la suite illisible.
2Initialisation
On vérifie $P(n_0)$ par un calcul explicite des deux membres. C'est court, mais indispensable : sans elle, la démonstration ne vaut rien.
3Hypothèse de récurrence
« Supposons que pour un certain entier $n\ge n_0$, $P(n)$ soit vraie. » On l'écrit en toutes lettres : c'est elle qu'on utilisera.
4Hérédité
On part du membre de gauche de $P(n+1)$, on y fait apparaître celui de $P(n)$ pour appliquer l'hypothèse, et on aboutit au membre de droite de $P(n+1)$.
5Conclusion
« $P(n_0)$ est vraie et $P$ est héréditaire, donc d'après le principe de récurrence, $P(n)$ est vraie pour tout $n\ge n_0$. »
Un exemple entièrement résolu
Démontrer par récurrence que pour tout entier $n\ge 1$ : $1+2+\cdots+n = \dfrac{n(n+1)}{2}$.
Pour tout $n\ge 1$, soit $P(n)$ : $\displaystyle\sum_{k=1}^{n}k = \dfrac{n(n+1)}{2}$.
Pour $n = 1$ : le membre de gauche vaut $1$, celui de droite $\dfrac{1\times 2}{2}=1$. $P(1)$ est vraie.
Supposons $P(n)$ vraie pour un certain $n\ge 1$. Alors :
$1+2+\cdots+n+(n+1) = \dfrac{n(n+1)}{2}+(n+1)$ par hypothèse de récurrence.
$= (n+1)\left(\dfrac{n}{2}+1\right) = (n+1)\times\dfrac{n+2}{2}=\dfrac{(n+1)(n+2)}{2}$, qui est bien le membre de droite de $P(n+1)$.
$P(1)$ est vraie et $P$ est héréditaire : par récurrence, $P(n)$ est vraie pour tout $n\ge 1$.
Conclusion. Pour tout entier $n\ge 1$, $1+2+\cdots+n = \dfrac{n(n+1)}{2}$.
Les erreurs à ne pas faire
- Sauter l'initialisation : une propriété héréditaire mais fausse au départ reste fausse partout.
- Utiliser $P(n+1)$ pour démontrer $P(n+1)$ : on part du membre de gauche, on n'a pas le droit de supposer l'égalité cherchée.
- Oublier d'écrire l'hypothèse de récurrence là où elle est utilisée : c'est le point que le correcteur cherche.
- Vérifier sur quelques valeurs et conclure : ce n'est pas une démonstration.
3 exercices pour s'entraîner
Cherche d'abord sur ton cahier, sans regarder l'exemple ; le corrigé se déplie ensuite.
- Exercice 1
Démontrer que pour tout $n\ge 0$, $2^n\ge n+1$.
Voir le corrigé
Initialisation : pour $n = 0$, $2^0 = 1$ et $0+1 = 1$ : vrai.
Hérédité : supposons $2^n\ge n+1$. Alors $2^{n+1} = 2\times 2^n\ge 2(n+1) = 2n+2$. Or $2n+2\ge n+2$ car $n\ge 0$. Donc $2^{n+1}\ge n+2$.
Conclusion : par récurrence, l'inégalité est vraie pour tout $n\ge 0$.
- Exercice 2
Soit $(u_n)$ définie par $u_0 = 1$ et $u_{n+1} = 3u_n+2$. Démontrer que $u_n = 2\times 3^n-1$.
Voir le corrigé
Initialisation : $u_0 = 1$ et $2\times 3^0-1 = 1$ : vrai.
Hérédité : si $u_n = 2\times 3^n-1$, alors $u_{n+1} = 3(2\times 3^n-1)+2 = 2\times 3^{n+1}-3+2 = 2\times 3^{n+1}-1$.
Conclusion : la formule est vraie pour tout $n$.
- Exercice 3
Soit $(u_n)$ définie par $u_0 = 0$ et $u_{n+1} = \sqrt{u_n+2}$. Démontrer que pour tout $n$, $0\le u_n\le 2$.
Voir le corrigé
Initialisation : $u_0 = 0$ vérifie bien $0\le 0\le 2$.
Hérédité : supposons $0\le u_n\le 2$. Alors $2\le u_n+2\le 4$, donc par croissance de la racine carrée $\sqrt{2}\le u_{n+1}\le 2$. En particulier $0\le u_{n+1}\le 2$.
Conclusion : l'encadrement est vrai pour tout $n$.
Questions fréquentes
Pourquoi l'initialisation est-elle indispensable ?
Parce que l'hérédité seule ne dit rien du point de départ. La propriété « $n$ est impair » est héréditaire au sens où si $n$ est impair alors $n+2$ l'est aussi, mais elle est fausse pour $n = 2$. L'hérédité propage une vérité ; encore faut-il qu'il y en ait une à propager.
Quand doit-on penser à une récurrence ?
Quand l'énoncé le demande explicitement, quand une propriété doit être établie « pour tout entier $n$ », ou quand une suite est définie par récurrence ($u_{n+1}$ en fonction de $u_n$) et qu'on veut en démontrer une borne, une monotonie ou une forme explicite.
Pour aller plus loin sur Mathovore
Cette fiche donne la méthode. Pour travailler le chapitre Suites en Terminale, voici le reste des ressources du site :