Le raisonnement par récurrence

Avant de commencer, regarde les vidéos

Épisode 1

1. Principe et illustration

Épisode 2

2. Exemples

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

Cette fiche de cours fait appel aux contenus suivants

Fonction racine carrée

Définition

Mathématiques