Conjecture puis récurrence

Dans ce cours, nous allons voir comment utiliser la démonstration par récurrence pour calculer la somme des entiers de 1 à n. La formule de la somme des entiers naturels est n(n + 1)/2. Pour utiliser la démonstration par récurrence, il faut connaître le résultat que l'on veut démontrer. Dans cet exemple, nous avons besoin de connaître la formule de la somme des entiers naturels. Nous commençons par poser la proposition p2n, qui est que la somme de 1 à n vaut n(n + 1)/2. Nous montrons ensuite que p2n est vrai pour tout n. Nous commençons par l'initialisation en vérifiant que la formule est vraie pour n = 1. Ensuite, nous passons à l'hérédité en supposant que p2n est vrai pour un n quelconque et nous voulons montrer que p2n+1 est vrai. Pour cela, nous remplaçons chaque occurrence de n par n + 1 dans l'expression au rang n. Nous appliquons la formule de la somme des entiers naturels à p2n et nous obtenons n(n + 1)/2 + n + 1. En simplifiant cette expression, nous obtenons n(n + 1)/2 + 2(n + 1)/2, ce qui donne (n + 1)(n + 2)/2. Ainsi, nous avons démontré que p2n+1 est vrai. En conclusion, d'après le principe de récurrence, nous avons prouvé que la somme des entiers de 1 à n est égale à n(n + 1)/2 pour tout entier naturel non nul n. C'est ainsi que nous pouvons utiliser la démonstration par récurrence pour calculer cette somme.