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