Le raisonnement par récurrence : Fiche de cours - Mathématiques

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$ est vraie pour tout entier naturel $n$ supérieur ou égal à un entier naturel $n$ 0 $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$ est vraie, c’est-à-dire que la proposition est vraie pour le premier indice $n$ 0 $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$ , $(P$ n) $(P_{n})$ est vraie, et sous cette hypothèse (dite de récurrence) on démontre que la proposition $(P$ est vraie. On a ainsi prouvé que l’hypothèse de récurrence « $(P$ n) $(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$ est vraie pour tout entier naturel $n (n > n$ 0) $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$ vraie » entraîne « $(P$ {n+1}) $(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$ définie par $u$ 0 = 1 $u_{0} = 1$ et pour tout entier naturel $n>0$ , $u$

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$ est croissante si pour tout entier naturel $n$ , $u$ n\leq u_{n+1} $u_{n} \leq u_{n + 1}$

Il s’agit de démontrer que $0 < u$

Commençons par noter $(P$ la proposition $0 < u$ n\leq u_{n+1} $0 < u_{n} \leq u_{n + 1}$

Initialisation

$u$ et $u$ 1 = \sqrt {u_0+1} = \sqrt {(1+1)} = \sqrt 2 $u_{1} = u_{0} + 1 = (1 + 1) = 2$

On a bien $0 <1 < \sqrt 2$ donc $0 < u$

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

Supposons la proposition $(P$ vraie pour un certain entier $n$ , c’est-à-dire : $0 < u$ n\leq u_{n+1} $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$ ), ce qui est équivalent, en utilisant la définition de la suite $(u_n)$ , à :

$0<\sqrt {u$

D’après l’hypothèse de récurrence :

$0 < u$

On ajoute 1 aux inégalités :

$1 < u$

Comme la fonction racine carrée est strictement croissante sur l’intervalle $[0\ ; +∞[$ , on obtient :

$\sqrt1<\sqrt {u$

Soit : $0 < 1 < u$

La propriété $(P_{n+1})$ est donc vraie.
Conclusion

Par récurrence, la proposition $(P$ est vraie pour tout entier naturel $n$ , donc la suite $(u$ n) $(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 \times 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$ la suite définie par $u$ 0= 2 $u_{0} = 2$ et pour tout entier naturel $n>0$ :

$u$

Démontrons que pour tout $n∈ \mathbb N$ , $u_n={\dfrac{2}{2n+1}}$

Notons $P$ la proposition « $u$ n={\dfrac{2}{2n+1}} $u_{n} = \frac{2}{2 n + 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$ , on a $u$ {n+1} ={ \dfrac{un}{1+un}} $u_{n + 1} = \frac{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}}$

Le raisonnement par récurrence

Le raisonnement par récurrence

Principe

Illustration

Exemples

Exemple 1

Exemple 2

Exemple 3

Contenus encyclopédiques liés : Idéal pour approfondir tes connaissances !