Démonstration par récurrence

01Comprendre

Pour établir une propriété P(n) pour tous les entiers à partir d’un rang, on vérifie d’abord l’initialisation. On démontre ensuite l’hérédité : pour un entier n arbitraire, si P(n) est vraie, alors P(n + 1) l’est aussi. La conclusion relie ces deux étapes. L’hypothèse de récurrence est utilisée dans une étape conditionnelle, sans supposer à l’avance que la propriété est vraie à tous les rangs. Une vérification sur dix valeurs ne remplace pas une preuve.

02Un exemple

Pour montrer 1 + … + n = n(n + 1)/2, l’initialisation au rang 1 donne 1. À l’étape suivante, on ajoute n + 1 à l’expression et on factorise pour obtenir (n + 1)(n + 2)/2.

03À toi de jouer

Quelle étape consiste à vérifier le premier rang ?

Correction : L’initialisation. On établit le point de départ de la chaîne de raisonnement.