Récurrence : somme des entiers

Énoncé

Montrer par récurrence que pour tout n 1 : _{k=1}^{n} k = n(n+1){2}.

Indice : Pose P(n) : « 1 + 2 + + n = n(n+1){2} ». Vérifie P(1), puis suppose P(n) et montre P(n+1).

Correction

1. Étape 1 : **Initialisation** (n=1) : _{k=1}^{1} k = 1 et 1 2{2} = 1. P(1) est vraie.
2. Étape 2 : **Hérédité** : supposons P(n) vraie, c'est-à-dire _{k=1}^{n} k = n(n+1){2}.
3. Étape 3 : _{k=1}^{n+1} k = n(n+1){2} + (n+1) = n(n+1) + 2(n+1){2} = (n+1)(n+2){2}. P(n+1) est vraie.
4. Étape 4 : **Conclusion** : par le principe de récurrence, P(n) est vraie pour tout n 1.