raisonnement par récurrence

Imaginez un carré de 4 × 4 carreaux. Pour obtenir un carré de 5 × 5, on lui ajoute une bordure en L de 9 carreaux. Le même geste fait passer chaque carré au suivant : au carré de côté n, on ajoute 2n + 1 carreaux.

Une preuve par récurrence suit cette idée de relais. Elle vérifie d'abord un point de départ, puis établit qu'une propriété vraie à un rang entraîne sa vérité au rang suivant. Le relais atteint alors tous les entiers à partir du rang choisi.

Le raisonnement par récurrence, aussi appelé induction mathématique, démontre une famille de propositions indexées par les entiers. On note P(n) la proposition associée à l'entier n et n₀ le premier rang considéré. L'initialisation consiste à prouver P(n₀). L'hérédité consiste à fixer un entier n supérieur ou égal à n₀, à supposer P(n) vraie, puis à en déduire P(n + 1). Cette supposition temporaire est l'hypothèse de récurrence.

Ces deux preuves permettent de conclure que P(n) est vraie pour tout entier n supérieur ou égal à n₀. En termes d'ensembles, les rangs où P est vraie forment une partie qui contient le rang initial et reste fermée par passage au successeur. Le principe de récurrence, lié à l'axiome de Péano, impose alors qu'elle contienne tous les rangs visés.

Le rang initial doit correspondre exactement au domaine annoncé. Si l'initialisation porte sur 1, la conclusion concerne les entiers n ≥ 1, et non automatiquement 0. Une récurrence forte autorise, dans l'étape héréditaire, l'emploi de toutes les propositions P(k) déjà établies pour les entiers k compris entre n₀ et n ; elle repose sur le même principe.

Montrons que la somme des n premiers nombres impairs vaut n² pour tout entier n ≥ 1. On appelle P(n) la proposition suivante, et le rang initial est 1.

1. Initialisation. Pour n = 1, la somme contient seulement 1, et 1 = 1². La proposition P(1) est vraie.

2. Hypothèse de récurrence. Fixons un entier n ≥ 1 et supposons P(n) vraie : la somme des n premiers impairs vaut n².

3. Hérédité. Le nombre impair suivant est 2(n + 1) − 1 = 2n + 1. En l'ajoutant à la somme précédente, on obtient l'égalité suivante.

Ainsi, P(n) entraîne P(n + 1).

4. Conclusion et contrôle. Par récurrence, l'identité est vraie pour tout entier n ≥ 1. Pour n = 4, 1 + 3 + 5 + 7 = 16 ; l'étape suivante ajoute 9 et donne 25 = 5². La construction par carreaux permet de refaire ce contrôle visuellement.

Pour établir une identité dépendant d'un entier, on écrit d'abord précisément P(n), puis on vérifie le premier rang. Dans l'exemple des nombres impairs, le passage de n à n + 1 isole le nouveau terme 2n + 1. Si la somme se simplifie directement par regroupement, un calcul algébrique peut être plus court.

Pour prouver une divisibilité ou une inégalité à tous les rangs, on cherche dans l'expression au rang n + 1 une partie contrôlée par l'hypothèse de récurrence. Si le passage au rang suivant ne réutilise pas P(n), une preuve directe ou un invariant adapté est préférable.

Avant de conclure, on contrôle trois points : le rang initial appartient au domaine, l'étape vaut pour chaque entier visé, et le pas relie bien n à n + 1. Ce contrôle repère la plupart des récurrences incomplètes.

Preuve par récurrence et suite définie par récurrence. La première démontre des propositions P(n) ; la seconde calcule un terme à partir de termes précédents. La règle u_n+1 = u_n + 2 définit une suite, mais ne prouve encore aucune propriété de cette suite.

Hypothèse de récurrence et raisonnement circulaire. Dans l'hérédité, P(n) est supposée seulement pour un entier n fixé afin d'établir l'implication vers P(n + 1). Affirmer d'emblée que P(n) est vraie pour tout n reviendrait, au contraire, à supposer la conclusion.

Induction mathématique et induction expérimentale. Vérifier P(1), P(2), P(3) fournit des observations, pas une preuve pour tous les entiers. La preuve devient générale seulement lorsque l'étape héréditaire couvre chaque rang du domaine.

Initialisation absente ou décalée. Prouver seulement P(n) ⇒ P(n + 1) ne lance pas la chaîne. Il faut établir le premier rang annoncé ; une preuve initialisée à n = 1 ne couvre pas n = 0.

Pas qui saute une classe d'entiers. Une implication P(n) ⇒ P(n + 2), initialisée uniquement à n = 1, atteint 1, 3, 5, puis les autres entiers impairs, mais aucun entier pair. Pour couvrir tous les entiers, il faut aussi initialiser la classe paire ou démontrer un pas de longueur 1.

Implication dans le mauvais sens. Déduire P(n) de P(n + 1) ne fait pas avancer depuis le rang initial. L'étape requise va du rang déjà atteint vers son successeur, sauf si une autre forme de récurrence est explicitement construite et initialisée.

Domaine non discret. Le pas n → n + 1 parcourt des entiers successifs ; il ne démontre pas, à lui seul, une propriété pour tout nombre réel. Sur un intervalle réel, il faut une méthode adaptée à la continuité ou aux propriétés de la fonction étudiée.

L'article Un orfèvre du raisonnement par récurrence prolonge la méthode par un regard centré sur la pratique du raisonnement.

La fiche Transfinie (récurrence) ouvre sur une extension de l'idée de récurrence au-delà des seuls entiers naturels.