Cours : Raisonnement par récurrence

Le raisonnement par récurrence

Principe

Pour démontrer par récurrence qu’une proposition $P$nPn​ 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${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.
• Hérédité

On suppose que, pour un entier naturel quelconque $k \geq n$0k≥n0​, $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$nPn​ est vraie pour tout entier naturel $n \geq n$0.

En effet :

• on a montré que $P${n0} est vraie ;
• on a démontré l’hérédité : si $P$kPk​ est vraie, alors $P${k+1} est vraie ;
• donc, avec $n=n$0n=n0​, $P${n_0+1} est vraie ;
• par hérédité, $P${(n0+1)+1}=P{n0+2} est vraie ;
• toujours par hérédité, $P${(n0+2)+1}=P{n0+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$nPn​ 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)(un​) définie par $u$0 = 1 et, pour tout entier naturel $n$, $u${n+1} = \sqrt{un + 1}.

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

Rappel

Une suite $(u$n)(un​) 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$nPn​ la proposition : $0 < u$n\leq u_{n+1}.
• Initialisation

$\begin{aligned} u$0 &= 1 \ \ u1 &= \sqrt {u_0 + 1} \ &= \sqrt {1+1} \ &= \sqrt 2 \end{aligned}

On a bien : $0 < 1 < \sqrt 2$, donc : $0 < u$0\leq u1.

• 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}Pk+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}

• 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$.

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$.

• 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)(un​) la suite définie par $u$0= 2 et, pour tout entier naturel $n$, $u${n+1} =\frac{un}{1+u_n}.

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

• Notons $P$nPn​ 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}$

• 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$

• 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$.