Démontrer une infinité d'énoncés en n'en vérifiant que deux choses : un premier pas, puis une règle qui fait passer de chaque pas au suivant.
Pour prouver qu'une propriété est vraie pour tous les entiers à partir d'un certain rang, on ne peut pas les essayer un par un : il y en a une infinité. On prouve à la place deux choses seulement : qu'elle est vraie au départ, et que, chaque fois qu'elle est vraie pour un entier, elle l'est aussi pour le suivant.
On note P(n) l'énoncé qui dépend de l'entier n (par exemple « 1 + 2 + … + n = n(n+1)/2 »), et n₀ le premier entier concerné.
Pourquoi est-ce légitime ? Parce que les entiers naturels sont exactement ce qu'on obtient en partant de 0 et en ajoutant 1, encore et encore : aucun entier n'échappe à cette file. Si la propriété est vraie au départ et se transmet d'un maillon au suivant, elle atteint chacun d'eux. C'est d'ailleurs ainsi que Peano a défini les entiers (voir la frise en fin de page). Les cinq planches montrent le mécanisme, des exemples types, le rôle du rang de départ, les erreurs classiques, puis la récurrence comme machine à construire.
Une file de dominos numérotés 1, 2, 3… Le domino n représente l'énoncé P(n), et « le domino tombe » veut dire « P(n) est démontré ». Pour que toute la file tombe, il faut que quelqu'un pousse le premier (initialisation) et que chaque domino, en tombant, renverse le suivant (hérédité). Retirez l'un ou l'autre et regardez ce qui reste démontré.
Premier exemple classique : la somme des n premiers entiers. La figure montre pourquoi la formule est plausible (deux escaliers identiques forment un rectangle) ; la récurrence prouve qu'elle est vraie pour tous les n, sans exception. Le bouton « Hérédité » rejoue l'étape clé : on part de la figure au rang n, on ajoute une seule colonne, et on retombe sur la formule au rang n+1.
Beaucoup d'inégalités ne sont vraies qu'« à partir d'un certain rang ». Dans la preuve de l'hérédité, on a souvent besoin d'une condition sur n (du genre « n ⩾ 3 »). Le point de départ n₀ doit donc réussir deux épreuves : P(n₀) vraie, et une hérédité valable pour tout n ⩾ n₀. Déplacez n₀ et observez jusqu'où la chaîne se propage.
Les deux étapes sont indispensables, et l'hérédité doit fonctionner pour chaque n, y compris le premier. Trois exemples célèbres montrent ce qui arrive quand on l'oublie : une hérédité impeccable qui ne démarre jamais, des vérifications à perte de vue qui ne prouvent rien, et une « démonstration » fausse dont un seul maillon est cassé.
Affirmation : « 10ⁿ + 1 est divisible par 9 ». Hérédité : si 9 divise 10ⁿ + 1, alors 10ⁿ⁺¹ + 1 = 10 × (10ⁿ + 1) − 9 est aussi divisible par 9. L'argument est juste ! Suivons le reste de la division par 9 sur le cadran.
À l'inverse, on peut vérifier une propriété sur des dizaines de cas sans qu'elle soit vraie en général : sans hérédité démontrée, les vérifications ne prouvent rien.
« Démonstration » célèbre (attribuée à George Pólya) que tous les chevaux ont la même couleur. P(n) : « dans tout groupe de n chevaux, tous ont la même couleur ». Initialisation : un groupe d'un cheval est bien unicolore. Hérédité : prenons n+1 chevaux ; les n premiers ont la même couleur (hypothèse), les n derniers aussi ; les deux groupes se chevauchent, donc tous ont la même couleur. Où est l'erreur ?
Une démonstration par récurrence n'est pas seulement un certificat : c'est très souvent une recette. L'hérédité dit comment fabriquer la solution au rang n+1 à partir de celle du rang n ; en la déroulant, on obtient un algorithme. Trois exemples, trois variantes : la récurrence simple (tours de Hanoï), la récurrence par découpage (pavage en triominos), et la récurrence forte, qui s'appuie sur plusieurs rangs précédents (les timbres).
But : déplacer la tour de la tige de gauche vers celle de droite, un disque à la fois, sans jamais poser un disque sur un plus petit. Propriété P(n) : « on sait déplacer n disques en 2ⁿ − 1 coups ». Hérédité : pour n+1 disques, on déplace les n du dessus sur la tige du milieu (possible par hypothèse, 2ⁿ − 1 coups), puis le grand disque (1 coup), puis les n disques par-dessus (2ⁿ − 1 coups) : total 2ⁿ⁺¹ − 1. La preuve est l'algorithme.
Un damier de 2ᵏ × 2ᵏ cases dont on a retiré une case peut-il être recouvert exactement par des triominos en L (trois cases) ? Oui, pour tout k, et la récurrence dit comment. On coupe le damier en quatre carrés de 2ᵏ⁻¹ ; celui qui contient le trou est pavable par hypothèse ; on pose un triomino au centre qui mord sur les trois autres carrés : chacun a désormais « son » trou, et l'hypothèse s'applique encore. Cliquez sur une case pour déplacer le trou.
Avec des timbres de 3 et de 5 centimes, peut-on affranchir n'importe quel montant ? Pas 1, 2, 4 ni 7 ; mais tout montant à partir de 8. Récurrence forte : on vérifie trois cas de base consécutifs (8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5), puis pour m ⩾ 11 on s'appuie sur m − 3 (déjà traité, puisque plus petit et au moins 8) et on ajoute un timbre de 3. L'hérédité ne remonte pas d'un rang, mais de trois : il faut donc trois initialisations.
« Pour tout entier n ⩾ n₀, on note P(n) : … — Initialisation : pour n = n₀, … donc P(n₀) est vraie. — Hérédité : soit n ⩾ n₀ tel que P(n) soit vraie ; montrons P(n+1). … — Conclusion : P(n₀) est vraie et P est héréditaire à partir du rang n₀, donc P(n) est vraie pour tout n ⩾ n₀. » Deux conseils : écrire noir sur blanc ce que l'on veut obtenir au rang n+1 avant de calculer, et signaler l'endroit précis où l'on utilise l'hypothèse de récurrence.
Récurrence double : quand la formule au rang n+2 utilise les rangs n et n+1 (suite de Fibonacci), on initialise sur deux rangs consécutifs. Récurrence forte : on suppose P(n₀), …, P(n) toutes vraies pour obtenir P(n+1) ; elle démontre par exemple que tout entier ⩾ 2 est un produit de nombres premiers. Descente infinie : équivalente au fait que toute partie non vide de ℕ a un plus petit élément (principe du bon ordre). Récurrence structurelle : en informatique, on raisonne de la même façon sur des arbres, des listes ou des formules, en suivant la manière dont ils sont construits. Récurrence transfinie : la théorie des ensembles prolonge le procédé au-delà des entiers, sur les ordinaux.
Elle ne trouve pas la formule : elle la confirme. Il faut d'abord la deviner (par des essais, une figure, un raisonnement), puis la récurrence la transforme en certitude. Le mot « induction » ne doit pas tromper : il ne s'agit pas de généraliser à partir d'exemples, ce qui serait l'erreur de la planche 4, mais d'une déduction parfaitement rigoureuse.