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 à $\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$ 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.
Initialisation

On vérifie que $P$ 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$ , $P$ k $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$ est vraie pour tout entier naturel $n \geq n$ 0 $n \geq n_{0}$ .

En effet :

on a montré que $P$ est vraie ;
on a démontré l’hérédité : si $P$ est vraie, alors $P$ {k+1} $P_{k + 1}$ est vraie ;
donc, avec $n=n$ , $P$ {n_0+1} $P_{n_{0} + 1}$ est vraie ;
par hérédité, $P$ est vraie ;
toujours par hérédité, $P$ 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$ vraie » entraîne « $P$ {n+1} $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$ définie par $u$ 0 = 1 $u_{0} = 1$ et, pour tout entier naturel $n$ , $u$ .

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

Il s’agit ici donc de démontrer que $0 < u$ , pour tout entier naturel $n$ .

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

$\begin{aligned} u$

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

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$

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

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

$0<\sqrt {u$

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\ ; +\,\infty[$ , elle ne change pas le sens des inégalités, et on obtient :	$\sqrt1<\sqrt {u$
Soit :	$0 < 1 < u$

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

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$ la suite définie par $u$ 0= 2 $u_{0} = 2$ et, pour tout entier naturel $n$ , $u$ .

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

Notons $P$ la proposition « $u$ n=\frac{2}{2n+1} $u_{n} = \frac{2}{2 n + 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$
Par définition de la suite :	$u{k+1} =\dfrac{u$
On remplace $u$ 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$
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.

Cours : Raisonnement par récurrence

Le raisonnement par récurrence

Principe

Illustration

Exemples

Exemple 1

Exemple 2

Exemple 3

Exemple 4 : inégalité de Bernoulli