Cours : 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.

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

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

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