Le raisonnement par récurrence : un exemple expliqué pas à pas

Énoncé : Montrer par récurrence que :
$\text{ Pour tout }n\in\mathbb{N}\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$

Puisqu'il s'agit d'un premier exemple, on va détailler (peut-être trop) en expliquant chaque étape. Nous exposerons ensuite une deuxième rédaction plus légère pour montrer comment bien rédiger un raisonnement par récurrence.

Résolution étape par étape bien détaillée aux fins d'explication :
Il faut montrer par récurrence que pour tout $n\in\mathbb{N} \text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$.

On pose pour cela : $\mathcal{P}(n)\text{ : } 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}$.
Et puisqu'il s'agit des entiers $n$ appartenant à $\mathbb{N}$, le premier rang est $0$ car il est le premier élément dans l'ensemble $\mathbb{N}$.

1. Initialisation : Pour $n=0\text{ : }\dfrac{0\times (0+1)}{2}=\dfrac{0\times 1}{2}=0$.
Donc la proposition $\mathcal{P}(0)$ est vraie.

Remarques :
$\circ$ La somme $0+1+2+\cdots+n$ veut dire qu'on additionne les nombres de $0$ à $n$
$\circ$ Donc pour le cas $n=0$, on additionne les nombres de $0$ à $0$, ce qui implique que la somme vaut $0$.
$\circ$On peut écrire les sommes en utilisant le symbole de la somme $\sum$.
On n'écrit pas $\mathcal{P}(0)=0$ car $\mathcal{P}(n)$ n'est pas un nombre qu'on calcule.

2. Hérédité : Soit $k\in\mathbb{N}$ un entier naturel.
Supposons que $\mathcal{P}(k)\text{ : } 0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$ est vraie, et montrons que dans ce cas, $\mathcal{P}(k+1)$ est vraie.
Pour pouvoir démontrer une propriété mathématique, il faut tout d'abord la connaître. Dans notre cas, il faut, avant de commencer, trouver ce qu'est l'expression de $\mathcal{P}(k+1)$.

En général, on remplace tout simplement $k$ dans l'expression de $\mathcal{P}(k)$ par $k+1$ pour trouver l'expression de $\mathcal{P}(k+1)$ :
(tenir le téléphone selon le mode paysage)
$\mathcal{P}(k+1) : 0+1+2+\cdots+(k+1)= \dfrac{(k+1)[(k+1)+1]}{2}$
On simplifie et on trouve : $\mathcal{P}(k+1) : 0+1+2+\cdots+(k+1)= \dfrac{(k+1)(k+2)}{2}$.
On va montrer que $0+1+2+\cdots+(k+1)= \dfrac{(k+1)(k+2)}{2}$ à partir de $\mathcal{P}(k) : 0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$.
Pour ne pas se perdre, on écrit dans un coin :
Hypothèse : $\mathcal{P}(k) : 0+1+2+\cdots+k= \dfrac{k(k+1)}{2}$.
Résultat à prouver : $\mathcal{P}(k+1) : 0+1+2+\cdots+(k+1)= \dfrac{(k+1)(k+2)}{2}$.
On sait que $0+1+2+\cdots+(k+1)=0+1+2+\cdots+k+(k+1)$, car elle est la somme de $0$ à $k+1$ et le nombre qui précède $k+1$ est $k$.
Donc :
$0+1+2+\cdots+(k+1)=\underbrace{0+1+2+\cdots+k}_{=\frac{k(k+1)}{2} \text{ d'après la supposition}}+(k+1)=\dfrac{k(k+1)}{2} + (k+1)=\dfrac{k(k+1)+2(k+1)}{2} =\dfrac{(k+1)(k+2)}{2}$
Donc on a bien $0+1+2+\cdots+(k+1)=\dfrac{(k+1)(k+2)}{2}$, ce qui montre que $\mathcal{P}(k+1)$ est vraie.

3. Conclusion : On a vu que la propriété était vraie au rang 0 et qu'elle est héréditaire, donc elle est vraie au rang 1, puis au rang 2... et ainsi de suite, elle est donc toujours vraie.
Par récurrence, on obtient : $\boxed{\text{ Pour tout }n\in\mathbb{N} : 0+1+2+\cdots+n= \dfrac{n(n+1)}{2}}$

Merci à Panter pour avoir contribué à l'élaboration de cette fiche.