Raisonnement par récurrence

information-icon

Si tu es un lycéen en terminale, tu dois déjà avoir planifié tes révisions pour ton baccalauréat 2024. 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 2024 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 à $\frac{n(n+1)}{2}$, c’est-à-dire que pour tout entier naturel $n> 0$ :

$$1+2+3+…+n =\dfrac{n(n+1)}{2}$$

Nous pouvons vérifier ce résultat pour $n=2$ et pour $n=3$ :

Pour $n = 2$ :

$\begin{aligned} 1+2&=3 \\ \dfrac{2(2+1)}{2} &= 3 \end{aligned}$

Pour $n = 3$ :

$\begin{aligned} 1+2+3&=6 \\ \dfrac{3(3+1)}{2} &= 6 \end{aligned}$

Même si ce résultat est vrai jusqu’à $n = 100$, cela ne démontre pas pour autant qu’il est vrai pour tout $n\in \mathbb 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.
  • Initialisation

On vérifie que $P_{n_0}$ 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.
  • Hérédité

On suppose que, pour un entier naturel quelconque $k \geq n_0$, $P_k$ est vraie.
Sous cette hypothèse (dite de récurrence), on démontre que la proposition $P_{k+1}$ est vraie.

  • On a ainsi prouvé que l’hypothèse de récurrence « $P_n$ vraie » est héréditaire.
  • Conclusion

Lorsque les deux premières étapes ont été réalisées, on peut conclure.

  • Par récurrence, la proposition $P_n$ est vraie pour tout entier naturel $n \geq n_0$.

En effet :

  • on a montré que $P_{n_0}$ est vraie ;
  • on a démontré l’hérédité : si $P_k$ est vraie, alors $P_{k+1}$ est vraie ;
  • donc, avec $n=n_0$, $P_{n_0+1}$ est vraie ;
  • par hérédité, $P_{(n_0+1)+1}=P_{n_0+2}$ est vraie ;
  • toujours par hérédité, $P_{(n_0+2)+1}=P_{n_0+3}$ est aussi vraie ;
  • et ainsi de suite…
  • C’est ce que l’on appelle un raisonnement par récurrence.

Illustration

Démontrons maintenant la formule vue en introduction à l’aide du raisonnement par récurrence et montrons que, pour tout entier naturel $n \in \mathbb N^*$, $1+…+ n = \frac{n(n+1)}{2}$.

  • Notons $P_n$ la proposition : $1+…+ n = \dfrac{n(n+1)}{2}$.
  • Initialisation

La proposition $P_1$ est vraie, car $1 = \dfrac{1(1+1)}{2} $.

On conçoit donc que, si l’on sait démontrer que, pour $n \geq 1$, « $P_n$ vraie » entraîne « $P_{n+1}$ vraie », alors la proposition est vraie pour tout entier naturel $n \geq 1$.

  • Hérédité

Supposons donc que $P_k$ est vraie pour un entier naturel $k \geq 1$, c’est-à-dire que, pour un entier naturel $k \geq 1$ :

$$1+2+… + (k-1) + k =\dfrac{k(k+1)}{2}$$

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la propriété est vraie au rang supérieur ($k+1$), c’est-à-dire que $P_{k+1}$ est vraie.
Autrement dit, montrons que :

$$1+2+…+k+(k+1) =\dfrac{(k+1)\big((k+1)+1\big)}{2}$$

Comme $P_k$ est vraie, dans la somme $1+2+…+k+(k+1)$, on peut remplacer les $k$ premiers termes par $\frac{k(k+1)}{2}$.

  • On obtient alors :

$$\begin{aligned} 1+2+…+k+(k+1)&=\overbrace{(1 + 2 + … + k)}^{ \frac{k(k+1)}{2}} + (k + 1) \\ &=\dfrac{k(k+1)}{2} + (k+1) \end{aligned}$$

  • En factorisant par $(k + 1)$, on obtient :

$$\begin{aligned} 1 + 2 + … + k + (k + 1)&= (k+1) \dfrac{k}{2} + (k+1) \\ &= {(k+1)}\Big( \dfrac{k}{2} +1\Big) \end{aligned}$$

  • En réduisant le deuxième facteur au même dénominateur $2$, on a :

$$\begin{aligned} 1 + 2 + … + k + (k + 1)&=(k+1)\dfrac{k+2}{2} \\ &=\dfrac{(k+1)\big((k+1)+1\big)}{2} \end{aligned}$$

  • Ainsi, $P_{k+1}$ est vraie.
  • Conclusion

$P_n$ est vraie pour tout entier naturel $n \geq 1$.

  • C’est-à-dire que, pour tout entier naturel $n \geq 1$ :

$$1 + … + n =\dfrac{n(n+1)}{2}$$

Exemples

La meilleure façon de se familiariser avec le raisonnement par récurrence, c’est de le travailler. Nous donnons donc ici quatre exemples d’un tel raisonnement.

  • N’hésitez pas à mener vous-même le raisonnement à partir de la formule à démontrer, avant de regarder le déroulé donné.

Exemple 1

On considère la suite $(u_n)$ définie par $u_0 = 1$ et, pour tout entier naturel $n$, $u_{n+1} = \sqrt{u_n + 1}$.

Montrons par récurrence que tous les termes de la suite $(u_n)$ sont strictement positifs et que la suite est croissante.

bannière rappel

Rappel

Une suite $(u_n)$ est croissante si, pour tout entier naturel $n$, $u_n\leq u_{n+1}$.

Il s’agit ici donc de démontrer que $0 < u_n\leq u_{n+1}$, pour tout entier naturel $n$.

  • Commençons par noter $P_n$ la proposition : $0 < u_n\leq u_{n+1}$.
  • Initialisation

$\begin{aligned} u_0 &= 1 \\ \\ u_1 &= \sqrt {u_0 + 1} \\ &= \sqrt {1+1} \\ &= \sqrt 2 \end{aligned}$

On a bien : $ 0 < 1 < \sqrt 2$, donc : $0 < u_0\leq u_1$.

  • La proposition $P_0$ est vraie.
  • Hérédité

Supposons la proposition $P_k$ vraie pour un certain entier naturel $k$, c’est-à-dire :

$$0 < u_k\leq u_{k+1}$$

  • C’est l’hypothèse de récurrence.

Montrons que la proposition $P_{k+1}$ est vraie, c’est-à-dire que $0 < u_{k+1}\leq u_{k+2}$.
En utilisant la définition de la suite $(u_n)$, c’est équivalent à :

$$0<\sqrt {u_k +1} \leq \sqrt{ u_{k+1} +1}$$

Hypothèse de récurrence : $0 < u_k\leq u_{k+1}$
On ajoute $1$ aux inégalités : $1 < u_k+1\leq u_{k+1}+1$
Comme la fonction racine carrée est strictement croissante sur l’intervalle $[0\ ; +\,\infty[$, elle ne change pas le sens des inégalités, et on obtient : $\sqrt1<\sqrt {u_k+1}\leq \sqrt { u_{k+1}+1}$
Soit : $0 < 1 < u_{k+1}\leq u_{k+2 }$
  • La propriété $P_{k+1}$ est donc vraie.
  • Conclusion

Par récurrence, la proposition $P_n$ est vraie pour tout entier naturel $n$.

  • La suite $(u_n)$ est croissante et à termes strictement positifs pour tout entier naturel $n$.

Exemple 2

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 :

$\begin{aligned} 4^0+2&=1+2 \\ &=3 \end{aligned}$

$3$ est bien divisible par $3$.

  • La proposition $P_0$ est vraie.
  • Hérédité

Supposons la proposition $P_k$ vraie pour un entier naturel $k$.

bannière astuce

Astuce

Pour montrer qu’un entier $x$ est divisible par un entier $a$, il faut montrer qu’il existe un entier $b$ tel que $x = a \times b$.

$(4^k+2)$ est divisible par $3$, c’est-à-dire qu’il existe un entier relatif $b$ tel que $4^k+2=3\times b$.

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la proposition $P_{k+1}$ est vraie, c’est à dire que $(4^{k+1}+2)$ est aussi divisible par $3$.

On cherche à montrer qu’il existe un entier relatif $c$ tel que $4^{k+1}+2 = 3 \times c$.

Hypothèse de récurrence : $4^k+2=3\times b$
On soustrait $2$ à l’égalité : $4^k=3\times b -2$
De plus : $4^{k+1}+2 = 4^k \times 4 +2$
On remplace $4^k$ par $(3 \times b - 2)$ : $4^{k+1}+2 =( 3\times b-2) \times 4 +2$
On développe : $\begin{aligned} 4^{k+1}+2 &= 12b-8+2 \\ &=12b-6 \end{aligned}$
On factorise par $3$ : $4^{k+1}+2 = 3 \times (4b -2)$
$b$ étant un entier relatif, $4b-2$ est donc aussi un entier relatif. Posons ainsi un entier relatif $c$ tel que $4b-2=c$. On obtient : $4^{k+1}+2 = 3 \times c$
  • Donc la proposition $P_{k+1}$ est vraie.
  • Conclusion

Pour tout entier naturel $n$, $P_n$ est vraie.

  • Pour tout entier naturel $n$, $4^n+2$ est divisible par $3$.

Exemple 3

Soit $(u_n)$ la suite définie par $u_0= 2$ et, pour tout entier naturel $n$, $u_{n+1} =\frac{u_n}{1+u_n}$.

Démontrons que, pour tout $n\in\mathbb N$, $u_n=\frac{2}{2n+1}$.

  • Notons $P_n$ la proposition « $u_n=\frac{2}{2n+1}$ ».
  • Initialisation

Pour $n = 0$ :

$\begin{aligned} u_0 &= 2 \\ \dfrac{2}{2 \times 0 +1} &= 2 \end{aligned}$

  • La proposition $P_0$ est vraie.
  • Hérédité

Supposons la proposition $P_k$ vraie pour un entier naturel $k$, c’est-à-dire que, pour un entier naturel $k$ :

$$u_k=\frac{2}{2k+1}$$

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la proposition est vraie au rang $(k + 1)$, c’est-à-dire :

$$u_{k+1}=\frac{2}{2(k+1)+1}$$

Hypothèse de récurrence : $u_k= \dfrac{2}{2k+1}$
Par définition de la suite : $u_{k+1} =\dfrac{u_k}{1+u_k}$
On remplace $u_k$ par $\dfrac{2}{2k+1}$ : $u_{k+1}= \dfrac{\frac{2}{2k+1}}{1+\frac{2}{2k+1}}$
On réduit au même dénominateur le dénominateur du deuxième terme : $\begin{aligned} u_{k+1}&= \dfrac{\frac{2}{2k+1}}{\frac{2k+1+2}{2k+1}} \\ &=\dfrac 2{2k+1}\times \dfrac {2k+1}{2k+1+2} \end{aligned}$
On simplifie par $(2k+1)$ : $u_{k+1}= \dfrac{2}{2k+2+1}$
On factorise $(2k+2)$ par $2$ : $u_{k+1}= \dfrac{2}{2(k+1)+1}$
  • Donc la proposition $P_{k+1}$ est vraie.
  • Conclusion

Pour tout entier naturel $n$, $P_n$ est vraie.

  • Pour tout entier naturel $n$, $u_n={\dfrac{2}{2n+1}}$.

Exemple 4 : inégalité de Bernoulli

L’inégalité de Bernoulli dit que, pour tout réel $x$ strictement positif et $n$ entier naturel, $(1+x)^n \geq 1 + nx$.

Nous utiliserons cette inégalité dans le cours suivant, sur les suites. Nous allons donc la démontrer ici, par récurrence.

Soit $x$ un réel strictement positif.

  • Notons $P_n$ la proposition « $(1+x)^n \geq 1 + nx$ ».
  • Initialisation

Pour $n = 0$ :

$\begin{aligned} (1+x)^0 &= 1 \\ & \geq 1 + 0\times x \end{aligned}$

  • Donc la proposition $P_0$ est vraie.
  • Hérédité

Supposons la proposition $P_k$ vraie pour un entier naturel $k$, c’est-à-dire, que pour un entier naturel $k$ :

$$(1+x)^k \geq 1 + kx$$

  • C’est l’hypothèse de récurrence.

Montrons maintenant que la proposition est vraie au rang $(k + 1)$, c’est-à-dire :

$$(1+x)^{k+1} \geq 1 + (k+1)x$$

On a : $(1+x)^{k+1} = (1+x)^k \times (1+x)$
Hypothèse de récurrence : ${(1+x)}^k \geq 1 + kx$
D’où, en multipliant par $(1+x)$ ($x>0$, donc $x+1>0$, et cela ne change pas le sens des inégalités) : $(1+x)^{k+1} \geq (1 + kx)(1 + x)$
On développe : $(1+x)^{k+1} \geq 1 + x + kx + k x^2$
On factorise $(x+kx)$ par $x$ : $(1+x)^{k+1} \geq 1 + x(k+1) + k x^2$
$k$ étant un entier positif, $kx^2\geq0$ : $ 1 + x(k+1) + k x^2 \geq 1 + (k+1)x$
D’où : ${(1+x)}^{k+1} \geq 1 + (k+1)x$
  • La proposition $P_{k+1}$ est vraie.
  • Conclusion

Pour tout entier naturel $n$, $P_n$ est vraie.

  • Pour tout entier naturel $n$ et tout réel $x$ strictement positif, $(1+x)^k \geq 1 + kx$.

Conclusion :

Dans ce cours, nous avons vu ce principe puissant qu’est le raisonnement par récurrence : il permet de démontrer assez rapidement une propriété sur l’ensemble des entiers naturels, ou une partie de cet ensemble.
Ainsi, notamment en travaillant sur les suites, nous ferons souvent appel à ce type de raisonnement.