Cours Le raisonnement par récurrence
Si tu es un lycéen en terminale, tu dois déjà avoir planifié tes révisions pour ton baccalauréat 2026. Si ce n’est pas le cas, tu peux te baser sur notre programme de révision en le planifiant en fonction des dates du bac 2026 ou des coefficients des matières … 💪
Introduction :
En mathématiques, un certain nombre de propriétés dépendent d’un entier naturel $n$.
Par exemple, la somme des entiers naturels de 1 à $n$ est égale à $\dfrac{n(n+1)}{2}$, c’est-à-dire que pour tout entier naturel $n$ :
$1+2+3+…+n =\dfrac{n(n+1)}{2}$
Vérification de ce résultat pour $n=2$ et pour $n=3$ :
- pour $n = 2$ :
$1+2=3 $ et $\dfrac{2(2+1)}{2} = 3 $
- pour $n = 3$ :
$1+2+3=6$ et $\dfrac{3(3+1)}{2} = 6 $
Même si on vérifie ce résultat jusqu’à $n = 100$, cela ne démontre pas qu’il est vrai pour tout $n$. Pour effectuer cette démonstration, on dispose d’un outil particulier : le raisonnement par récurrence.
Le raisonnement par récurrence
Principe
Pour démontrer par récurrence qu’une proposition $(P_n)$ est vraie pour tout entier naturel $n$ supérieur ou égal à un entier naturel $n_0$ fixé, on procède en trois étapes.
Avant de commencer, on note $(P_n)$ la proposition que l’on va démontrer.
- Étape 1 : Initialisation
On vérifie que $(P_{n0})$ est vraie, c’est-à-dire que la proposition est vraie pour le premier indice $n_0$. On dit qu’on a initialisé la récurrence.
- Étape 2 : Hérédité
On suppose que pour un entier $n$ quelconque $n > n_0$, $(P_n)$ est vraie, et sous cette hypothèse (dite de récurrence) on démontre que la proposition $(P_{n+1})$ est vraie. On a ainsi prouvé que l’hypothèse de récurrence « $(P_n)$ vraie » est héréditaire.
- Étape 3 : Conclusion
Lorsque les deux premières étapes ont été réalisées, on conclut : par récurrence, la proposition $(P_n)$ est vraie pour tout entier naturel $n (n > n_0)$.
Illustration
Démonstration de la formule vue en introduction à l’aide du raisonnement par récurrence :
Montrons que pour tout entier naturel $n$, $1+2+3+4+…+ n = \dfrac{n(n+1)}{2}$
Notons $(P_n)$ la proposition : $1+2+3+4+…+ n = \dfrac{n(n+1)}{2}$
- Étape 1 : Initialisation
La proposition $(P_1)$ est vraie car $1 = \dfrac{1(1+1)}{2} $
On conçoit et on admet que si l’on sait démontrer que « $(P_n)$ vraie » entraîne « $(P_{n+1})$ vraie », alors la proposition est vraie pour tout entier naturel $n > 0$.
- Étape 2 : Hérédité
Supposons donc que $(P_n)$ est vraie pour un entier naturel $n$, c’est-à-dire que pour un entier naturel $n$ :
$1+2+3+4+… + n-1 + n =\dfrac{n(n+1)}{2}$
- C’est l’hypothèse de récurrence.
Montrons maintenant que la propriété est vraie au rang supérieur (au rang $n+1$), c’est-à-dire que $(P_{n+1})$ est vraie.
Autrement dit, montrons que :
$1+2+3+…+n+(n+1) =\dfrac{(n+1)(n+2)}{2}$
Comme $(P_n)$ est vraie, alors dans la somme $1+2+3+…+n+(n+1)$, on peut remplacer les $n$ premiers termes par $\dfrac{n(n+1)}{2}$
On obtient alors :
- $1 + 2 + 3\;+\;… n + n + 1 = {\dfrac{n(n+1)}{2} } + n+1 $
En factorisant par $n + 1$, on obtient :
- $\begin{aligned}1 + 2 + 3\;+\;… +\;n + (n + 1) &= {(n+1) { \dfrac{n}{2} } } + (n+1) \\&= {(n+1)}( \dfrac{n}{2} +1) \end{aligned}$
En réduisant le deuxième facteur au même dénominateur 2, on a :
- $1 + 2 + 3\;+\;… +\;n + n + 1 = $ $\dfrac{(n+1)(n+2)}{2}$
Ainsi $(P_{n+1})$ est vraie.
- Étape 3 : Conclusion
$(P_n)$ est vraie pour tout entier naturel $n > 0$, c’est-à-dire pour tout entier naturel $n$, $1+2+3\;+\;…+\;n =$ $\dfrac{n(n+1)}{2}$
Exemples
Exemple 1
Exemple
On considère la suite $(u_n)$ définie par $u_0 = 1$ et pour tout entier naturel $n>0$, $u_n+1 = \sqrt{u_{n+1}}$
On montre par récurrence que tous les termes de la suite $(un)$ sont strictement positifs et que la suite est croissante.
Rappel
Une suite $(u_n)$ est croissante si pour tout entier naturel $n$, $u_n\leq u_{n+1}$
Il s’agit de démontrer que $0 < u_n\leq u_{n+1}$
Commençons par noter $(P_n)$ la proposition $0 < u_n\leq u_{n+1}$
- Initialisation
$u_0 = 1$ et $u_1 = \sqrt {u_0+1} = \sqrt {(1+1)} = \sqrt 2 $
On a bien $ 0 <1 < \sqrt 2 $ donc $0 < u_0\leq u_1$
- Donc la proposition $P_0$ est vraie.
- Hérédité
Supposons la proposition $(P_n)$ vraie pour un certain entier $n$, c’est-à-dire : $0 < u_n\leq u_{n+1}$
- C’est l’hypothèse de récurrence.
Montrons que la proposition $(P{n+1})$ est vraie (c’est-à-dire : $0 < u_{n+1}\leq u_{n+2 }$), ce qui est équivalent, en utilisant la définition de la suite $(u_n)$, à :
$0<\sqrt {u_n+1} \leq {\sqrt{ u_{n+1} +1}} $
D’après l’hypothèse de récurrence :
$0 < u_n\leq u_{n+1}$
On ajoute 1 aux inégalités :
$1 < u_n+1\leq u_{n+1}+1$
Comme la fonction racine carrée est strictement croissante sur l’intervalle $[0\ ; +∞[$, on obtient :
$\sqrt1<\sqrt {u_n+1}\leq \sqrt { u_{n+1}+1}$
Soit : $0 < 1 < u_{n+1}\leq u_{n+2 }$
- La propriété $(P_{n+1})$ est donc vraie.
- Conclusion
Par récurrence, la proposition $(P_n)$ est vraie pour tout entier naturel $n$, donc la suite $(u_n)$ est croissante et à termes strictement positifs pour tout entier naturel $n$.
Exemple 2
Exemple
Démontrons que pour tout entier naturel $n$ : $4^n+2$ est divisible par $3$.
Notons $P_n$ la proposition « $4^n+2$ est divisible par $3$ ».
- Initialisation
Pour $n = 0$, on a $4^0+2=1+2=3$ et $3$ est bien divisible par $3.$
- Donc la proposition $P_0$ est vraie.
- Hérédité
Supposons la proposition $P_n$ vraie pour un entier $n$.
- Conclusion
On a alors $4^n+2$ est divisible par $3$, c’est-à-dire qu’il existe un nombre $b$ tel que $4^n+2=3\times b$
- C’est l’hypothèse de récurrence.
Astuce
Pour montrer qu’un nombre $x$ est divisible par un entier $a$, il faut montrer qu’il existe un nombre $b$ tel que $x = a \times b$
Montrons maintenant que la proposition $P_n$ est vraie au rang $n+1$, c’est à dire que $4^{n+1}+2$ est aussi divisible par $3$.
- On cherche à montrer qu’il existe un entier $k$ tel que $4^{n+1}+2 = 3 \times k$
On a : $4^n+2=3\times b$
- On soustrait $2$ à l’égalité :
$4^n=3\times b -2$
- De plus :
$4^{n+1}+2 = 4^n \times 4 +2$
- On remplace $4^n$ par $(3 × b - 2)$ :
$4^{n+1}+2 =( 3\times b-2) \times 4 +2$
- On développe :
$\begin{aligned}4^{n+1}+2 &=( 3\times b-2) \times 4 +2 \\ &= 12b-8+2 \\ &=12b-6\end{aligned}$
- On factorise par $3$ :
$4^{n+1}+2 = 3 \times (4b -2)$
Comme le nombre $4b - 2$ est un entier alors on a bien $4^{n+1}+2=3\times k$ en posant $k = 4b - 2$
- Donc la proposition $P_{n+1}$ est vraie.
- Conclusion
Par récurrence, pour tout entier naturel $n$, $P_n$ est vraie, donc pour tout entier naturel $n$, $4^n+2$ est divisible par $3$.
Exemple 3
Exemple
Soit $(u_n)$ la suite définie par $u_0= 2$ et pour tout entier naturel $n>0$ :
$u_{n+1} ={ \dfrac{u_n}{1+u_n}}$
Démontrons que pour tout $n∈ \mathbb N$, $u_n={\dfrac{2}{2n+1}}$
Notons $P_n$ la proposition « $u_n={\dfrac{2}{2n+1}}$ »
- Initialisation
Pour $n = 0$, $u_0 = 2$ et ${\dfrac{2}{2 \times 0 +1} } = 2$
Donc la proposition $P_0$ est vraie.
- Hérédité
Supposons la proposition $Pn$ vraie pour un entier $n$, c’est-à-dire que pour un entier $n$, $u_n={\dfrac{2}{2n+1}}$
- C’est l’hypothèse de récurrence.
On montre maintenant que la proposition est vraie au rang $n + 1$, c’est-à-dire que $u_{n+1}={\dfrac{2}{2(n+1)+1}}$
Par définition de la suite $u_n$, on a $u_{n+1} ={ \dfrac{u_n}{1+u_n}}$ et d’après l’hypothèse de récurrence cela donne : $u_{n+1}= { \dfrac{{\dfrac{2}{2n+1}}}{1+{\dfrac{2}{2n+1}}} } $
En réduisant au même dénominateur et en simplifiant par $2n + 1$, on obtient :
$u_{n+1}={\dfrac{2}{2n+1+2}}$
ce qui est égal à $u_{n+1}={\dfrac{2}{2(n+1)+1}}$
- Donc la proposition $P_{n+1}$ est vraie.
- Conclusion
Par récurrence, pour tout entier naturel $n$, $P_n$ est vraie, c’est-à-dire que pour tout entier naturel $n$ :
$u_n={\dfrac{2}{2n+1}}$
