Raisonnement par récurrence

Pour démontrer par récurrence qu’une proposition $\text{P}(n)$ est vraie pour tout entier naturel $n\geqslant n_0$, on procède en trois étapes :

1. Initialisation

On vérifie que la proposition est vraie au premier ordre, c’est-à-dire que $\text{P}(n_0)$ est vraie.

2. Hérédité

$\blacktriangleright$ On suppose dans un premier temps qu’il existe un entier $n$, $n\geqslant n_0$, tel que la proposition $\text{P}(n)$ soit vraie (c’est l’hypothèse de récurrence) ;

$\blacktriangleright$ On démontre ensuite, sous cette hypothèse, que la proposition $\text{P}(n+1)$ est vraie.

 

On aura alors démontré que la proposition $\text{P}(n)$ est héréditaire.

3. Conclusion

Les deux étapes précédentes ayant été réalisées, on conclut :

$\text{P}(n_0)$ est vraie et la proposition est héréditaire donc, d’après le principe de récurrence, $\text{P}(n)$ est vraie pour tout entier naturel $n\geqslant n_0$.

Exemple:


Démontrez que pour tout entier $n\geqslant 1$, $\quad 1^3+2^3+ … +n^3=\dfrac{n^2(n+1)^2}{4}.$


Considérons la proposition $\text{P}(n) :$ « $1^3+2^3+ … +n^3=\dfrac{n^2(n+1)^2}{4}$ ».

Démontrons par récurrence que $\text{P}(n)$ est vraie pour tout entier naturel $n\geqslant 1$

1. Initialisation

Vérifions que $\text{P}(1)$ est vraie :

Pour $n=1$, le membre de gauche de l’égalité n’a qu’un seul terme, $1^3$ et  $1^3=1$ et le membre de droite vaut $\dfrac{1^2(1+1)^2}{4}=\dfrac{1\times 2^2}{4}=\dfrac{4}{4}=1$.

Ainsi pour $n=1$ on a bien l’égalité des deux membres :  $1^3=\dfrac{1^2(1+1)^2}{4}$ .

$\text{P}(1)$ est donc vraie.

2. Hérédité

$\blacktriangleright$ Supposons que $\text{P}(n)$ est vraie pour un entier $n\geqslant 1$.

Démontrons alors que $\text{P}(n+1)$ est vraie, c’est-à-dire que $1^3+2^3+ … +n^3+(n+1)^3=\dfrac{(n+1)^2(n+2)^2}{4}.$

$\blacktriangleright$ Par hypothèse de récurrence, nous avons $\quad 1^3+2^3+ … +n^3=\dfrac{n^2(n+1)^2}{4}$.

Ajoutons $(n+1)^3$ à chacun des membres de l’égalité précédente, nous obtenons alors $1^3+2^3+ … +n^3+(n+1)^3=\dfrac{n^2(n+1)^2}{4}+(n+1)^3$.

Soit, en mettant au même dénominateur les termes du second membre

$\begin{eqnarray}1^3+2^3+ … +n^3+(n+1)^3 &=& \dfrac{n^2(n+1)^2}{4}+(n+1)^3 \nonumber \\ &=& \dfrac{n^2(n+1)^2}{4}+\dfrac{4(n+1)^3}{4}\nonumber \\ &=& \dfrac{n^2(n+1)^2+4(n+1)^3}{4}\nonumber \end{eqnarray}$

En remarquant, dans le second membre de l’égalité, que le facteur $\color{green}{(n+1)^2}$ est commun aux deux termes du numérateur :

$\begin{eqnarray}1^3+2^3+ … +n^3+(n+1)^3 &=& \dfrac{\color{orange}{n^2}\color{green}{(n+1)^2}\color{violet}{+}\color{orange}{4}\color{green}{(n+1)^2}\color{orange}{(n+1)}}{4}\nonumber\end{eqnarray}$

nous pouvons factoriser par $\color{green}{(n+1)^2}$ et obtenir

$\begin{eqnarray}1^3+2^3+ … +n^3+(n+1)^3 &=& \dfrac{\color{green}{(n+1)^2}\color{black}{(}\color{orange}{n^2\color{violet}{+}\color{orange}{4(n+1)}\color{black}{)}}}{4}\nonumber \\ &=&\dfrac{(n+1)^2(n^2+4n+4)}{4}\nonumber \end{eqnarray}$

Arrivé ici, pour pouvoir continuer, il faut connaître ses identités remarquables.

En effet il faut remarquer que, dans le membre de droite, le facteur $(n^2+4n+4)$ peut se mettre sous forme factorisée $(n+2)^2$.

On obtient alors finalement :

$\begin{eqnarray}1^3+2^3+ … +n^3+(n+1)^3 &=& \dfrac{(n+1)^2(n+2)^2}{4}\nonumber.\end{eqnarray}$

$\text{P}(n+1)$ est donc vraie.

Ainsi, en supposant $\text{P}(n)$ vraie, nous avons démontré que $\text{P}(n+1)$ est vraie.

« $\text{P}(n)$ vraie » est donc héréditaire.

3. Conclusion

$\text{P}(1)$ est vraie et « $\text{P}(n)$ vraie » est héréditaire donc, d’après le principe de récurrence, $\text{P}(n)$ est vraie pour tout entier naturel $n\geqslant 1$.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.