La récurrence forte

Dans ce cours, Paul explique comment utiliser le raisonnement par récurrence pour démontrer une relation de récurrence forte. Il donne l'exemple d'une suite u1 définie par u1 = 3 et la somme des n premiers termes de la suite divisée par deux fois n pour toute n. On veut démontrer que pour toute n, u1 est égale à 3n. Paul définit une propriété pn (récurrence forte) pour montrer que tous les uk sont égaux à 3k et pas seulement u1 = 3n. Il effectue ensuite une initialisation (n = 1) et démontre l'hérédité pour n + 1 en deux cas: k appartient à 1 à n et k = n + 1. Lorsque k appartient à 1 à n, la propriété est prouvée car on sait que tous les uk sont égaux à 3k grâce à pn. Ensuite, en remplacant les ui par 3j, on obtient la somme des j allant de 0 à n, qui est égale à n(n+1)/2. Après avoir simplifié, on obtient 3n, ce qui prouve que pn + 1 est vrai. Ainsi, pn est vrai pour tout n et un est égal à 3n pour tout n.