Induction

Imaginez une rangée de dominos numérotés à partir de 1. Le premier tombe, et chaque domino qui tombe fait tomber le suivant. Ces deux faits suffisent pour entraîner toute la rangée.

Une preuve par récurrence suit le même mouvement. Elle vérifie d'abord la propriété au rang de départ, puis établit que sa vérité à un rang entraîne sa vérité au rang suivant.

Le raisonnement par récurrence, aussi appelé principe d'induction, démontre une propriété portant sur tous les entiers naturels à partir d'un entier fixé. On note P(n) l'énoncé à prouver au rang entier n. L'initialisation établit P(n₀) au rang de départ n₀. L'hérédité prouve que, pour tout entier n au moins égal à n₀, l'hypothèse P(n) entraîne P(n + 1). Ces deux étapes permettent alors de conclure que P(n) est vraie pour tout entier n ≥ n₀.

Dans une récurrence forte, l'étape d'hérédité suppose vraies toutes les propriétés P(k) pour les entiers k compris entre n₀ et n, afin d'établir P(n + 1). Cette variante n'est pas plus puissante sur les entiers naturels, mais son hypothèse correspond mieux à certaines constructions. Le principe repose sur la structure des entiers naturels formalisée par les axiomes de Peano.

On veut prouver la formule donnant la somme des entiers de 1 à n. Données : n est un entier au moins égal à 1 ; P(n) est l'affirmation ${\sum }_{k=1}^{n}k=\frac{n(n+1)}{2}\backslash sum\_\{k=1\}^\{n\}\; k=\backslash frac\{n(n+1)\}\{2\}$, où k est l'indice parcourant les entiers additionnés.

1. Initialisation. Au rang 1, le membre de gauche vaut 1 et le membre de droite vaut 1 × 2 ÷ 2 = 1. La propriété P(1) est donc vraie.

2. Hypothèse de récurrence. Fixons un entier n ≥ 1 et supposons P(n) vraie. Cette supposition ne porte que sur ce rang arbitraire.

3. Hérédité. En ajoutant n + 1 aux deux membres, on obtient : ${\sum }_{k=1}^{n+1}k=\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}\backslash sum\_\{k=1\}^\{n+1\}\; k=\backslash frac\{n(n+1)\}\{2\}+(n+1)=\backslash frac\{(n+1)(n+2)\}\{2\}$. C'est exactement P(n + 1). La chaîne logique relie ainsi chaque rang au suivant.

4. Conclusion. L'initialisation et l'hérédité prouvent la formule pour tout entier n ≥ 1.

Un contrôle au rang 4 donne 1 + 2 + 3 + 4 = 10, tandis que 4 × 5 ÷ 2 = 10. Ce calcul vérifie un cas sans remplacer la démonstration générale.

Pour prouver une identité indexée par un entier, on choisit le premier rang annoncé, puis on transforme l'expression du rang n en celle du rang n + 1. Si un calcul direct vaut pour tout n sans hypothèse de rang, il est souvent plus court.

Pour établir qu'un algorithme répété conserve une propriété après chaque étape, le rang compte le nombre d'itérations. Une preuve par invariant est préférable lorsque l'état évolue sans se ramener naturellement au passage de n à n + 1.

Pour une suite définie à partir de plusieurs termes précédents, la récurrence forte rend disponibles tous les rangs déjà construits. La récurrence simple suffit si seul le rang immédiatement précédent intervient.

Induction mathématique et induction empirique. La première enchaîne des implications démontrées sur les entiers ; la seconde généralise à partir d'observations. Vérifier la formule de la somme pour n = 1, 2, 3 et 4 fournit des exemples, mais pas une preuve par récurrence.

Récurrence et relation de récurrence. Le raisonnement par récurrence est une méthode de preuve. Une relation de récurrence définit ou relie des termes successifs d'une suite. L'égalité u_n+1 = u_n + 2 définit une évolution ; elle ne démontre encore aucune propriété de la suite.

Initialisation manquante. Une implication P(n) ⇒ P(n + 1) peut être vraie sans qu'aucun rang ne lance la chaîne. Il faut toujours vérifier le rang de départ annoncé.

Mauvais rang de départ. Si l'énoncé vise les entiers n ≥ 2, vérifier seulement P(1) ne suffit pas lorsque l'hérédité n'est établie qu'à partir de n = 2. Il faut initialiser au premier rang couvert par l'implication.

Hypothèse utilisée comme conclusion. Dans l'hérédité, P(n) est provisoirement supposée vraie pour un entier n arbitraire ; P(n + 1) doit être déduite de cette hypothèse, et non affirmée sous une nouvelle supposition.

Domaine troué. Le passage de n à n + 1 parcourt des entiers consécutifs. Pour une propriété limitée aux entiers pairs, il faut reformuler l'indice ou prouver un passage de n à n + 2 avec les initialisations nécessaires.

La Transfinie (récurrence) prolonge l'idée d'induction à des ordres qui dépassent les seuls entiers naturels.

L'article Un orfèvre du raisonnement par récurrence replace cette méthode dans une lecture mathématique plus incarnée.