-
On considère une propriété P(n)\mathcal{P}(n) é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 P(0)\mathcal{P}(0) est vraie.
Le second, la démonstration du caractère héréditaire de la propriété, consiste à montrer que si P(n)\mathcal{P}(n) est vraie pour un entier naturel n quelconque, alors P(n+1)\mathcal{P}(n + 1) 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 P(n)\mathcal{P}(n) 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 P(0)\mathcal{P}(0) et P(1)\mathcal{P}(1) sont vraies, puis que si P(n−1)\mathcal{P}(n - 1) et P(n)\mathcal{P}(n) sont vraies alors P(n+1)\mathcal{P}(n + 1) l’est aussi. On peut même aller jusqu’à une « récurrence forte » où, pour montrer que P(n+1)\mathcal{P}(n + 1) est vraie, on suppose que la propriété est vraie pour tous les rangs inférieurs.