Exercice : Raisonnement par Récurrence

Raisonnement par Récurrence

On souhaite démontrer par récurrence la propriété suivante, pour tout entier naturel n ≥ 0 :

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

Étape 1 : Initialisation

On vérifie que la propriété est vraie pour le premier rang, ici n=0.

Pour n=0, la somme des entiers de 0 à 0 est :

Et n(n+1)/2 = 0(0+1)/2 = 0. Donc P(0) est vraie.

Étape 2 : Hérédité

On suppose que P(k) est vraie pour un certain entier k ≥ 0 (Hypothèse de récurrence).

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

Complétez le raisonnement :

0 + 1 + ... + k + (k+1) = (0 + 1 + ... + k) + (k+1)

Ensuite, on met (k+1) en facteur : (k+1) * (k/2 + 1) = (k+1) * ((k+2)/2) = (k+1)(k+2)/2

On a bien démontré P(k+1).

Étape 3 : Conclusion

P(n) est initialisée pour n=0 et est héréditaire. Donc, par le principe de récurrence, la propriété P(n) est vraie pour tout entier naturel n ≥ 0.