Le raisonnement par récurrence se fait en trois étapes que sont l’initialisation, l’hérédité et la conclusion. Ces trois étapes sont nécessaires pour mener à bien un tel raisonnement que nous allons illustrer à partir d’un exemple.
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$.
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 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 , on obtient :
- $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.
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}$,