La récurrence

Définition

La récurrence démontre qu'une propriété $P(n)$P(n) vaut pour tout entier à partir d'un rang $n_0$n0​, au moyen de deux vérifications seulement :

Ces deux points établissent une infinité d'énoncés. C'est là leur force : on ne vérifie jamais qu'un cas et une implication.

Une image, et sa limite

Une file de dominos : faire tomber le premier, et garantir que chacun renverse le suivant, suffit à les faire tous tomber.

L'image est juste sur le mécanisme et fausse sur la portée. Une file de dominos est finie et la chute prend du temps ; la récurrence porte sur une infinité de rangs et ne se déroule pas. Elle ne raconte pas une propagation, elle prouve une propriété.

Un exemple mené jusqu'au bout

Montrons que la somme des $n$n premiers entiers vaut $\dfrac{n(n+1)}{2}$2n(n+1)​.

Initialisation. Pour $n = 1$n=1 : la somme vaut 1, et $\dfrac{1 \times 2}{2} = 1$21×2​=1.

Hérédité. Supposons la formule vraie au rang $n$n. Alors :

$1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$1+2+⋯+n+(n+1)=2n(n+1)​+(n+1)=2n(n+1)+2(n+1)​=2(n+1)(n+2)​

C'est la formule au rang $n+1$n+1. Les deux étapes tiennent, la propriété vaut pour tout $n \geq 1$n≥1.

Les deux étapes sont nécessaires

L'hérédité seule ne prouve rien. Prenons $P(n)$P(n) : « $n = n + 1$n=n+1 ».

Cette propriété est héréditaire : si $n = n+1$n=n+1, alors en ajoutant 1 des deux côtés, $n + 1 = n + 2$n+1=n+2. Le pas se propage parfaitement — et la propriété est fausse pour tout entier, parce qu'aucun rang ne l'amorce.

L'initialisation seule ne suffit pas davantage : une propriété peut être vraie en 1 et fausse ensuite.

Récurrence forte

Certaines démonstrations réclament plus que le rang précédent. La récurrence forte suppose $P(k)$P(k) pour tous les $k \leq n$k≤n, et non pour le seul $n$n.

Elle sert lorsque le pas fait appel à un rang bien antérieur — décomposer un entier en facteurs premiers, par exemple, renvoie à deux facteurs quelconques plus petits, pas au prédécesseur.

Résumé

Un point de départ et un pas qui se propage démontrent une infinité de cas ; ni l'un ni l'autre ne s'en passe.