Conjecture puis récurrence

Dans ce cours, nous avons vu comment utiliser une démonstration par récurrence pour calculer la somme des entiers de 1 à n. La formule à retenir est que la somme des entiers naturels de 1 à n est égale à n(n + 1)/2. Il est important de noter que pour utiliser cette méthode de démonstration, il faut connaître le résultat que l'on souhaite démontrer. Si vous n'avez aucune idée de la valeur de la somme des entiers naturels, vous ne pourrez pas poursuivre la démonstration. Dans cet exemple, nous allons redémontrer cette formule. Nous posons la proposition p(2n) suivante : 1 + 2 + 3 + ... + n = n(n + 1)/2. Nous supposons que p(2n) est vrai pour tout n appartenant à l'ensemble des entiers naturels. Nous commençons par l'initialisation en vérifiant que la formule est vraie pour n = 1. En effet, 1 = 1(1 + 1)/2, donc cela est vérifié. Ensuite, nous passons à l'hérédité. Nous supposons que p(2n) est vrai pour un certain n fixé. Nous souhaitons montrer que p(2n + 1) est également vrai, c'est-à-dire que 1 + 2 + ... + (n + 1) = (n + 1)(n + 2)/2. Pour cela, nous remplaçons chaque occurrence de n par (n + 1) dans la formule au rang n. Nous obtenons donc (n + 1)(n + 1 + 1)/2, ce qui se simplifie en (n + 1)(n + 2)/2. Ainsi, en appliquant cette méthode de manière itérative, nous parvenons à démontrer que pour tout entier naturel non nul n, la somme des entiers de 1 à n est égale à n(n + 1)/2.