Raisonnement par récurrence
Ce chapitre fait partie du programme de Terminale.
Le raisonnement par récurrence permet de démontrer qu'une propriété est vraie pour tous les entiers naturels à partir d'un certain rang, alors qu'on ne peut pas vérifier une infinité de cas un par un. On s'en sert pour les suites définies par récurrence, pour les inégalités et pour les formules de sommes.
Prérequis
- Suites numériques (classe de 1re) : définition explicite et par récurrence, calcul des premiers termes, sens de variation
- Calcul littéral : développer, factoriser, réduire au même dénominateur
- Manipulation d'inégalités : ajouter un nombre, multiplier par un nombre positif ou négatif
- Sens de variation d'une fonction et effet d'une fonction croissante sur une inégalité
- Puissances : $a^{n+1}=a\times a^n$
À la fin du chapitre, on sait
- Énoncer le principe de récurrence et comprendre le rôle de chaque étape
- Rédiger une démonstration par récurrence complète : initialisation, hérédité, conclusion
- Démontrer par récurrence l'expression explicite, un encadrement ou le sens de variation d'une suite définie par $u_{n+1}=f(u_n)$
- Démontrer l'inégalité de Bernoulli et d'autres inégalités par récurrence
- Démontrer des formules de sommes écrites avec le symbole $\sum$
- Repérer les erreurs de rédaction et les faux raisonnements par récurrence
1.Le principe de récurrence
On veut parfois démontrer qu'une affirmation est vraie pour tous les entiers $n$ : par exemple « $4^n-1$ est divisible par $3$ ». Vérifier $n=0$, $n=1$, $n=2$, … ne suffit jamais : il reste une infinité de cas.
L'idée est celle d'une rangée de dominos. Si le premier tombe, et si chaque domino qui tombe fait tomber le suivant, alors tous les dominos tombent. Le raisonnement par récurrence traduit exactement ces deux conditions.
Propriété dépendant d'un entier
Soit $n_0$ un entier naturel. On note $P(n)$ une proposition qui dépend de l'entier $n\geq n_0$ : pour chaque valeur de $n$, elle est soit vraie, soit fausse.
Exemples :
- $P(n)$ : « $2^n\geq n+1$ » ;
- $P(n)$ : « $u_n=2^{n+1}-1$ » ;
- $P(n)$ : « $0\leq u_n\leq 2$ ».
$P(n)$ est une phrase, pas un nombre. On écrit « $P(n)$ : … » et jamais « $P(n)=\ldots$ ».
Principe de récurrence
Soit $n_0\in\mathbb{N}$ et $P(n)$ une proposition définie pour tout entier $n\geq n_0$. On suppose que :
- Initialisation : $P(n_0)$ est vraie ;
- Hérédité : pour tout entier $n\geq n_0$, si $P(n)$ est vraie, alors $P(n+1)$ est vraie.
Alors $P(n)$ est vraie pour tout entier $n\geq n_0$.
Statut du principe
Ce principe est admis en Terminale. Il traduit une propriété fondamentale de l'ensemble $\mathbb{N}$ : en partant de $n_0$ et en ajoutant $1$ autant de fois que nécessaire, on atteint tout entier $n\geq n_0$.
Dans l'hérédité, la phrase « $P(n)$ est vraie » s'appelle l'hypothèse de récurrence. On l'abrège souvent en HR.
Ce que dit vraiment l'hérédité
L'hérédité est une implication : $P(n)\Rightarrow P(n+1)$. Elle n'affirme pas que $P(n)$ est vraie. Elle affirme seulement que, si $P(n)$ l'était, alors $P(n+1)$ le serait aussi.
C'est l'initialisation qui fournit le premier cas vrai. Sans elle, l'hérédité seule ne prouve rien (voir la dernière section).
2.Rédiger une démonstration par récurrence
Le squelette d'une récurrence
Pour démontrer qu'une propriété est vraie pour tout $n\geq n_0$ :
- Énoncer la propriété : « Pour tout entier $n\geq n_0$, on note $P(n)$ : … ». Préciser $n_0$.
- Initialisation : vérifier $P(n_0)$. Calculer séparément chaque membre, puis comparer.
- Hérédité : écrire « Soit $n\geq n_0$ un entier fixé. On suppose $P(n)$ vraie. Montrons que $P(n+1)$ est vraie. » Écrire explicitement ce que dit $P(n+1)$ : c'est le but à atteindre. Partir de la quantité qui apparaît dans $P(n+1)$, la relier à celle de $P(n)$, utiliser l'hypothèse de récurrence en le signalant.
- Conclusion : « La propriété est vraie au rang $n_0$ et elle est héréditaire, donc d'après le principe de récurrence, $P(n)$ est vraie pour tout entier $n\geq n_0$. »
Expression explicite d'une suite
Soit $(u_n)$ définie par $u_0=1$ et $u_{n+1}=2u_n+1$ pour tout $n\in\mathbb{N}$. Les premiers termes sont $1,\ 3,\ 7,\ 15$ : on conjecture $u_n=2^{n+1}-1$.
Pour tout $n\in\mathbb{N}$, on note $P(n)$ : « $u_n=2^{n+1}-1$ ».
Initialisation. $u_0=1$ et $2^{0+1}-1=2-1=1$. Donc $P(0)$ est vraie.
Hérédité. Soit $n\in\mathbb{N}$ fixé. On suppose $u_n=2^{n+1}-1$. Montrons que $u_{n+1}=2^{n+2}-1$. $$u_{n+1}=2u_n+1=2\left(2^{n+1}-1\right)+1=2^{n+2}-2+1=2^{n+2}-1.$$ La deuxième égalité utilise l'hypothèse de récurrence. Donc $P(n+1)$ est vraie.
Conclusion. $P(0)$ est vraie et la propriété est héréditaire, donc pour tout $n\in\mathbb{N}$, $u_n=2^{n+1}-1$.
Une divisibilité
Montrons que, pour tout $n\in\mathbb{N}$, $4^n-1$ est divisible par $3$.
On note $P(n)$ : « il existe un entier $k$ tel que $4^n-1=3k$ ».
Initialisation. $4^0-1=0=3\times 0$. Donc $P(0)$ est vraie.
Hérédité. Soit $n\in\mathbb{N}$ fixé. On suppose qu'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+3=3(4k+1).$$ Comme $4k+1$ est un entier, $4^{n+1}-1$ est divisible par $3$ : $P(n+1)$ est vraie.
Conclusion. Par récurrence, $4^n-1$ est divisible par $3$ pour tout $n\in\mathbb{N}$.
Quand penser à la récurrence
On pense à une récurrence lorsque la propriété porte sur un entier $n$ et que le passage de $n$ à $n+1$ est simple : une suite définie par $u_{n+1}=f(u_n)$, une puissance $a^{n+1}=a\times a^n$, une somme qui s'obtient en ajoutant un terme.
La récurrence ne sert pas à tout. Si $u_n=3n+2$, on a directement $u_{n+1}-u_n=3$ : aucune récurrence n'est nécessaire.
3.Récurrence et suites définies par récurrence
On considère une suite définie par $u_{n_0}$ donné et $u_{n+1}=f(u_n)$, où $f$ est une fonction. On ne connaît en général pas de formule explicite pour $u_n$. La récurrence permet pourtant d'obtenir des informations : un encadrement, le signe, le sens de variation.
Encadrer une suite et étudier ses variations avec une fonction croissante
Pour une suite $u_{n+1}=f(u_n)$, on cherche souvent à démontrer $P(n)$ : « $a\leq u_n\leq u_{n+1}\leq b$ ».
- Étudier $f$ et vérifier qu'elle est croissante sur un intervalle contenant $[a\,;b]$.
- Initialisation : calculer $u_{n_0}$ et $u_{n_0+1}$, vérifier l'encadrement.
- Hérédité : partir de $a\leq u_n\leq u_{n+1}\leq b$ et appliquer $f$, qui conserve l'ordre : $f(a)\leq u_{n+1}\leq u_{n+2}\leq f(b)$.
- Calculer $f(a)$ et $f(b)$ et vérifier que $f(a)\geq a$ et $f(b)\leq b$ pour retrouver $a\leq u_{n+1}\leq u_{n+2}\leq b$.
- Conclure : la suite est croissante, minorée par $a$, majorée par $b$.
Si on obtient $u_{n+1}\leq u_n$ à l'initialisation, on démontre de même $a\leq u_{n+1}\leq u_n\leq b$ : la suite est alors décroissante.
Une suite avec une racine carrée
Soit $(u_n)$ définie par $u_0=1$ et $u_{n+1}=\sqrt{u_n+2}$. On pose $f(x)=\sqrt{x+2}$ sur $[-2\,;+\infty[$.
La fonction $f$ est croissante sur $[-2\,;+\infty[$ : c'est la composée de $x\mapsto x+2$, croissante, suivie de la racine carrée, croissante.
Pour tout $n\in\mathbb{N}$, on note $P(n)$ : « $0\leq u_n\leq u_{n+1}\leq 2$ ».
Initialisation. $u_0=1$ et $u_1=\sqrt{3}$. Comme $1\leq 3\leq 4$, on a $1\leq\sqrt{3}\leq 2$, donc $0\leq u_0\leq u_1\leq 2$ : $P(0)$ est vraie.
Hérédité. Soit $n\in\mathbb{N}$ fixé. On suppose $0\leq u_n\leq u_{n+1}\leq 2$. Ces nombres sont dans $[-2\,;+\infty[$ où $f$ est croissante, donc $$f(0)\leq f(u_n)\leq f(u_{n+1})\leq f(2),\quad\text{soit}\quad \sqrt{2}\leq u_{n+1}\leq u_{n+2}\leq 2.$$ Comme $\sqrt{2}\geq 0$, on obtient $0\leq u_{n+1}\leq u_{n+2}\leq 2$ : $P(n+1)$ est vraie.
Conclusion. Pour tout $n\in\mathbb{N}$, $0\leq u_n\leq u_{n+1}\leq 2$. La suite $(u_n)$ est croissante et majorée par $2$.
Une suite arithmético-géométrique
Soit $u_0=0$ et $u_{n+1}=0{,}5u_n+3$. Montrons que $u_n\leq 6$ pour tout $n\in\mathbb{N}$.
On note $P(n)$ : « $u_n\leq 6$ ».
Initialisation. $u_0=0\leq 6$.
Hérédité. Soit $n\in\mathbb{N}$ fixé, on suppose $u_n\leq 6$. En multipliant par $0{,}5>0$ : $0{,}5u_n\leq 3$. En ajoutant $3$ : $u_{n+1}\leq 6$.
Conclusion. Pour tout $n\in\mathbb{N}$, $u_n\leq 6$.
On en déduit le sens de variation sans nouvelle récurrence : $$u_{n+1}-u_n=3-0{,}5u_n=0{,}5(6-u_n)\geq 0.$$ La suite est croissante.
Variations de $f$ et variations de la suite
Le sens de variation de $f$ ne donne pas directement celui de $(u_n)$. Avec $f(x)=\dfrac{x}{2}$, croissante :
- si $u_0=1$, alors $u_1=0{,}5<u_0$ et la suite est décroissante ;
- si $u_0=-1$, alors $u_1=-0{,}5>u_0$ et la suite est croissante.
C'est la comparaison de $u_0$ et $u_1$, propagée par récurrence, qui donne le sens de variation.
Si $f$ est décroissante, appliquer $f$ renverse les inégalités et la méthode précédente ne s'applique pas telle quelle.
Vers la convergence
Dans l'exemple de la racine carrée, la suite est croissante et majorée. Le théorème de convergence monotone, vu dans le chapitre sur les limites de suites, permet d'en déduire qu'elle converge. La récurrence fournit donc souvent la première étape d'une étude de convergence.
4.Démontrer des inégalités : l'inégalité de Bernoulli
Inégalité de Bernoulli
Soit $a$ un nombre réel positif. Pour tout entier naturel $n$, $$(1+a)^n\geq 1+na.$$
Démonstration (exigible)
Soit $a\geq 0$ fixé. Pour tout $n\in\mathbb{N}$, on note $P(n)$ : « $(1+a)^n\geq 1+na$ ».
Initialisation. $(1+a)^0=1$ et $1+0\times a=1$. Comme $1\geq 1$, $P(0)$ est vraie.
Hérédité. Soit $n\in\mathbb{N}$ fixé. On suppose $(1+a)^n\geq 1+na$. Montrons que $(1+a)^{n+1}\geq 1+(n+1)a$.
Comme $a\geq 0$, on a $1+a>0$. On multiplie les deux membres de l'hypothèse de récurrence par $1+a$, ce qui conserve le sens de l'inégalité : $$(1+a)^{n+1}\geq (1+na)(1+a).$$ Or $$(1+na)(1+a)=1+a+na+na^2=1+(n+1)a+na^2.$$ Puisque $n\geq 0$ et $a^2\geq 0$, on a $na^2\geq 0$, donc $(1+na)(1+a)\geq 1+(n+1)a$.
Par transitivité, $(1+a)^{n+1}\geq 1+(n+1)a$ : $P(n+1)$ est vraie.
Conclusion. $P(0)$ est vraie et la propriété est héréditaire. Par récurrence, pour tout $n\in\mathbb{N}$, $(1+a)^n\geq 1+na$.
Une hypothèse plus faible suffit
Dans la démonstration, on a seulement utilisé $1+a\geq 0$ (pour multiplier sans changer le sens) et $na^2\geq 0$, qui est toujours vrai. L'inégalité reste donc vraie pour tout réel $a\geq -1$, avec la même preuve.
Application : limite de $q^n$ pour $q>1$
Soit $q>1$. On pose $a=q-1$, donc $a>0$ et $q=1+a$. D'après l'inégalité de Bernoulli, pour tout $n\in\mathbb{N}$ : $$q^n\geq 1+na.$$ Comme $a>0$, $\lim\limits_{n\to+\infty}(1+na)=+\infty$. Par le théorème de comparaison, $\lim\limits_{n\to+\infty}q^n=+\infty$.
C'est la démonstration attendue de ce résultat du chapitre sur les limites de suites.
Démontrer une inégalité par récurrence
Dans l'hérédité d'une inégalité, on obtient rarement $P(n+1)$ en une seule ligne. On procède en chaîne :
- Partir de la quantité de gauche au rang $n+1$ et l'exprimer à l'aide de celle du rang $n$ (par exemple $2^{n+1}=2\times 2^n$).
- Utiliser l'hypothèse de récurrence pour obtenir une première inégalité $A\geq B$.
- Démontrer à part une seconde inégalité $B\geq C$, où $C$ est la quantité visée. On étudie pour cela le signe de $B-C$.
- Conclure par transitivité : $A\geq C$.
À chaque multiplication d'une inégalité, vérifier le signe du facteur.
Comparer $2^n$ et $n^2$
Montrons que, pour tout entier $n\geq 4$, $2^n\geq n^2$. On note $P(n)$ : « $2^n\geq n^2$ ».
Initialisation. Pour $n=4$ : $2^4=16$ et $4^2=16$. Donc $P(4)$ est vraie.
Hérédité. Soit $n\geq 4$ un entier fixé. On suppose $2^n\geq n^2$. Montrons que $2^{n+1}\geq (n+1)^2$.
En multipliant l'hypothèse de récurrence par $2>0$ : $2^{n+1}\geq 2n^2$.
Comparons $2n^2$ et $(n+1)^2$ : $$2n^2-(n+1)^2=n^2-2n-1=(n-1)^2-2.$$ Comme $n\geq 4$, $(n-1)^2\geq 9$, donc $(n-1)^2-2\geq 7>0$. Ainsi $2n^2\geq (n+1)^2$.
Par transitivité, $2^{n+1}\geq (n+1)^2$ : $P(n+1)$ est vraie.
Conclusion. Pour tout entier $n\geq 4$, $2^n\geq n^2$.
Le rang $n_0=4$ n'est pas un détail : pour $n=3$, $2^3=8<9=3^2$. La propriété est vraie pour $n=0,1,2$ mais fausse pour $n=3$ ; l'hérédité échoue à partir de $n=2$ car $(2-1)^2-2=-1<0$.
5.Démontrer des formules de sommes
Le symbole somme
Pour des nombres $u_1,u_2,\ldots,u_n$, on note $$\sum_{k=1}^{n}u_k=u_1+u_2+\cdots+u_n.$$ La lettre $k$ est muette : $\sum_{k=1}^{n}k^2$ et $\sum_{i=1}^{n}i^2$ désignent le même nombre.
Relation clé pour les récurrences : si $S_n=\sum_{k=1}^{n}u_k$, alors $$S_{n+1}=S_n+u_{n+1}.$$
Somme des premiers entiers
Pour tout entier $n\geq 1$, $$\sum_{k=1}^{n}k=1+2+\cdots+n=\frac{n(n+1)}{2}.$$
Démonstration par récurrence
Pour $n\geq 1$, on note $P(n)$ : « $\sum_{k=1}^{n}k=\dfrac{n(n+1)}{2}$ ».
Initialisation. Pour $n=1$ : la somme vaut $1$ et $\dfrac{1\times 2}{2}=1$. $P(1)$ est vraie.
Hérédité. Soit $n\geq 1$ fixé. On suppose $\sum_{k=1}^{n}k=\dfrac{n(n+1)}{2}$. Montrons que $\sum_{k=1}^{n+1}k=\dfrac{(n+1)(n+2)}{2}$. $$\sum_{k=1}^{n+1}k=\sum_{k=1}^{n}k+(n+1)=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}.$$ La dernière égalité s'obtient en factorisant par $n+1$ : $(n+1)\left(\dfrac{n}{2}+1\right)=(n+1)\dfrac{n+2}{2}$. $P(n+1)$ est vraie.
Conclusion. Par récurrence, la formule est vraie pour tout $n\geq 1$.
Somme des premiers nombres impairs
Montrons que, pour tout $n\geq 1$, $\sum_{k=1}^{n}(2k-1)=1+3+\cdots+(2n-1)=n^2$.
Initialisation. Pour $n=1$ : $2\times 1-1=1=1^2$.
Hérédité. Soit $n\geq 1$ fixé, on suppose $\sum_{k=1}^{n}(2k-1)=n^2$. Le terme ajouté au rang $n+1$ est $2(n+1)-1=2n+1$. Donc $$\sum_{k=1}^{n+1}(2k-1)=n^2+2n+1=(n+1)^2.$$
Conclusion. Pour tout $n\geq 1$, $1+3+\cdots+(2n-1)=n^2$.
Somme des carrés
Montrons que, pour tout $n\geq 1$, $$\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6}.$$
Initialisation. Pour $n=1$ : la somme vaut $1$ et $\dfrac{1\times 2\times 3}{6}=1$.
Hérédité. Soit $n\geq 1$ fixé, on suppose la formule vraie au rang $n$. Le but est $\sum_{k=1}^{n+1}k^2=\dfrac{(n+1)(n+2)(2n+3)}{6}$. $$\begin{aligned}\sum_{k=1}^{n+1}k^2&=\frac{n(n+1)(2n+1)}{6}+(n+1)^2\\&=\frac{(n+1)\left[n(2n+1)+6(n+1)\right]}{6}\\&=\frac{(n+1)(2n^2+7n+6)}{6}.\end{aligned}$$ Or $(n+2)(2n+3)=2n^2+3n+4n+6=2n^2+7n+6$. Donc $\sum_{k=1}^{n+1}k^2=\dfrac{(n+1)(n+2)(2n+3)}{6}$.
Conclusion. La formule est vraie pour tout $n\geq 1$.
Hérédité d'une formule de somme
- Écrire le but : la formule au rang $n+1$, avec le membre de droite où $n$ est remplacé par $n+1$.
- Isoler le dernier terme : $S_{n+1}=S_n+u_{n+1}$.
- Remplacer $S_n$ grâce à l'hypothèse de récurrence.
- Factoriser par le facteur commun attendu (souvent $n+1$) plutôt que tout développer.
- Comparer avec le but en développant, si besoin, le membre de droite du but.
La récurrence vérifie, elle ne trouve pas
Une récurrence démontre une formule déjà connue ou conjecturée. Pour la conjecturer, on calcule les premières valeurs, souvent à la calculatrice ou avec un programme Python, puis on cherche une régularité.
6.Erreurs de rédaction et faux raisonnements
Une hérédité sans initialisation
On note $P(n)$ : « $10^n+1$ est divisible par $9$ ».
L'hérédité fonctionne : si $10^n+1=9k$ avec $k$ entier, alors $10^n=9k-1$ et $$10^{n+1}+1=10(9k-1)+1=90k-9=9(10k-1).$$ Pourtant $P(n)$ est fausse pour tout $n$ : $10^0+1=2$, et pour $n\geq 1$, l'écriture décimale de $10^n+1$ comporte deux chiffres $1$ et des $0$, donc la somme de ses chiffres vaut $2$, qui n'est pas divisible par $9$.
Sans initialisation, aucun domino ne tombe : l'hérédité seule ne prouve rien.
Des vérifications sans hérédité
On pose $p(n)=n^2-n+41$. On vérifie que $p(n)$ est un nombre premier pour $n=0,1,2,\ldots,40$. On pourrait croire que $p(n)$ est toujours premier.
Or $p(41)=41^2-41+41=41^2$, qui n'est pas premier.
Vérifier un grand nombre de cas ne remplace pas l'hérédité.
Ne pas supposer ce qu'on veut démontrer
Écrire « Supposons que $P(n)$ est vraie pour tout $n$ » au début de l'hérédité est faux : c'est la conclusion qu'on cherche. On écrit : « Soit $n\geq n_0$ un entier fixé. On suppose $P(n)$ vraie. »
De même, il ne faut pas partir de $P(n+1)$ et en déduire une égalité vraie : on démontrerait $P(n+1)\Rightarrow\ldots$, ce qui est l'implication dans le mauvais sens.
Autres erreurs de forme
- Écrire « $P(n)=\dfrac{n(n+1)}{2}$ » : $P(n)$ est une phrase, pas un nombre.
- Initialiser au mauvais rang : si la propriété est demandée pour $n\geq 1$, ou si elle n'est vraie qu'à partir de $n=4$, il faut initialiser à ce rang.
- Oublier d'utiliser l'hypothèse de récurrence : si elle ne sert pas, soit la récurrence est inutile, soit le calcul est faux.
- Oublier la conclusion : elle fait partie de la démonstration et rapporte des points au baccalauréat.
Hors programme : d'autres formes de récurrence
Il existe des variantes : la récurrence double (on suppose $P(n)$ et $P(n+1)$ pour obtenir $P(n+2)$, avec deux initialisations) et la récurrence forte (on suppose $P(n_0),\ldots,P(n)$ vraies). Elles sont hors programme en Terminale et étudiées en classes préparatoires. Au baccalauréat, seule la récurrence simple est attendue.