Le raisonnement par récurrence est un outil aussi classique qu'indispensable dont la formulation se résume facilement.
On considère une propriété )
énoncée pour un certain entier naturel n. Pour démontrer que cette propriété est vraie pour tout entier naturel, on peut procéder en deux temps.
Le premier, l’initialisation, consiste à démontrer que )
est vraie.
Le second, la démonstration du caractère héréditaire de la propriété, consiste à montrer que si est vraie pour un entier naturel n quelconque, alors )
est vraie aussi. On illustre souvent ce principe par une rangée de domino qui tombent les uns après les autres quand on a poussé le premier.
Il existe plusieurs raffinements de ce principe, qui restent cependant équivalents à cette « récurrence simple ». On peut bien sûr initialiser le raisonnement à partir d’un entier non nul n0 et on conclura que est vraie pour tout entier nsupérieur ou égal à n0. On peut aussi mettre en œuvre une « récurrence double » ; dans ce cas, on démontre que et )
sont vraies, puis que si )
et sont vraies alors l’est aussi. On peut même aller jusqu’à une « récurrence forte » où, pour montrer que est vraie, on suppose que la ...
Lire la suite gratuitement
