Savoir mener un raisonnement par récurrence

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}$,