Une démonstration complète : la somme des n premiers entiers

L'énoncé à démontrer

On veut démontrer que, pour tout entier naturel n >= 1, la propriété P(n) suivante est vraie :

P(n) : 1 + 2 + 3 + ... + n = n(n+1)/2

Étape 1 - Initialisation (rang n = 1)

On vérifie P(1) : la somme à gauche se réduit à 1 (un seul terme). À droite, on calcule 1x(1+1)/2 = 1x2/2 = 1. Les deux membres valent 1, donc P(1) est vraie.

Étape 2 - Hérédité

On suppose que P(k) est vraie pour un entier k >= 1 fixé, c'est-à-dire que l'on suppose :

1 + 2 + ... + k = k(k+1)/2 (hypothese de recurrence)

On veut démontrer que P(k+1) est vraie, c'est-à-dire que 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.

Calcul de l'heredite, terme par terme :

1 + 2 + ... + k + (k+1)

  = [1 + 2 + ... + k] + (k+1)
  = k(k+1)/2 + (k+1)             (on utilise l'hypothese de recurrence ici)
  = (k+1) x [ k/2 + 1 ]
  = (k+1) x [ (k+2)/2 ]
  = (k+1)(k+2)/2                 (c'est exactement ce qu'on voulait montrer)

On a donc bien montré que P(k) vraie entraîne P(k+1) vraie.

Conclusion

Par le principe de récurrence, comme P(1) est vraie (initialisation) et que P(k) vraie entraîne P(k+1) vraie pour tout k >= 1 (hérédité), on conclut que P(n) est vraie pour tout entier n >= 1.

Vérification numérique

Pour n = 4 : la somme 1+2+3+4 = 10, et la formule donne 4x5/2 = 20/2 = 10. Pour n = 7 : la somme 1+2+3+4+5+6+7 = 28, et la formule donne 7x8/2 = 56/2 = 28. Les deux méthodes concordent.

Piège classique

Dans l'étape d'hérédité, il faut bien UTILISER l'hypothèse de récurrence à un moment précis du calcul (ici, en remplaçant "1 + 2 + ... + k" par "k(k+1)/2") : une hérédité qui ne s'appuie jamais sur l'hypothèse P(k) n'a en général aucune chance d'aboutir, et signale souvent une erreur de rédaction.