Logique

Le raisonnement par récurrence : du particulier au général

Observer des cas particuliers permet de deviner ; seule la récurrence permet de démontrer. Un premier cas vérifié, une règle de passage d’un rang au suivant démontrée une fois pour toutes, et l’énoncé tient pour tous les entiers.

Deux sens du mot « induction »

Dans la langue courante, l’induction est le passage du particulier au général : le Soleil s’est levé chaque matin, donc il se lèvera demain. Ce raisonnement est fécond, mais ce n’est pas une preuve : un seul contre-exemple suffit à le ruiner. Ce que les mathématiciens anglophones appellent mathematical induction, et que l’on nomme en France raisonnement par récurrence, est tout autre chose : il ne généralise pas des exemples, il enchaîne deux démonstrations.

Initialisation. On vérifie que l’énoncé P(n₀) est vrai pour un premier entier n₀.

Hérédité. On démontre, pour un entier n ⩾ n₀ quelconque, que si P(n) est vrai, alors P(n+1) est vrai.

Conclusion. P(n) est vrai pour tout entier n ⩾ n₀.

Dire seulement « si l’énoncé est vrai pour n, il est vrai pour n+1 » ne suffit pas. L’hérédité est une implication : elle transmet la vérité d’un rang au suivant, elle ne la crée pas. Sans un premier cas vérifié, elle ne prouve rien (planche 3). Et le cas particulier de départ n’est pas un « exemple » dont on généralise : c’est le premier maillon d’une chaîne dont chaque maillon suivant est démontré.

L’échelle infinie. Initialisation : on pose le pied sur le premier barreau (vert). Hérédité : de n’importe quel barreau, on sait monter au suivant (flèches rouges). Décochez l’une ou l’autre pour voir l’ascension s’arrêter.

Initialisation le premier barreau est atteint

Hérédité

Barreaux atteints

—

	Induction au sens courant	Raisonnement par récurrence
Point de départ	des cas particuliers observés	un cas particulier vérifié (l’initialisation)
Passage au général	on étend ce que l’on a vu	on démontre, pour un n quelconque, que P(n) entraîne P(n+1)
Statut du résultat	conjecture, qu’un contre-exemple peut réfuter	théorème, valable pour tous les entiers à partir de n₀
Dans cette page	planche 1 (les régions du cercle)	planches 2 à 5

Cinq cas qui trompent : les régions du cercle

Question : suffit-il d’observer beaucoup de cas pour être sûr ? Placez n points sur un cercle et tracez toutes les cordes qui les relient. Combien de régions découpent-elles dans le disque ? Pour 1, 2, 3, 4, 5 points on trouve 1, 2, 4, 8, 16 : tout le monde parie sur 2ⁿ⁻¹. Passez à 6 points. Ce problème est dû au mathématicien Leo Moser.

Cordes en bleu, dernière corde tracée en rouge, points de croisement en violet. Un point rouge cerclé signale au moins trois cordes concourantes.

Nombre de points n6

Points régulièrement espacés

Régions comptées (Euler : arêtes − sommets + 1)

—

Règle de la corde (chaque corde ajoute croisements + 1)

—

Formule 1 + C(n,2) + C(n,4)

—

Conjecture 2ⁿ⁻¹

—

Points où ⩾ 3 cordes concourent

—

Régions à l’étape du tracé

—

Échelle logarithmique. Bleu : régions réellement comptées (points en position générale) ; orange : la conjecture 2ⁿ⁻¹. Contrôle comptage − formule pour n = 1 à 12 : —.

Ce que l’on vient de voir. Cinq cas particuliers s’accordent parfaitement avec 2ⁿ⁻¹, le sixième donne 31 au lieu de 32, et l’écart devient énorme ensuite (562 régions pour 12 points contre 2 048). L’induction au sens courant fabrique des conjectures, jamais des preuves. Cochez « points régulièrement espacés » avec n = 6 : trois diagonales passent par le centre et l’on ne trouve plus que 30 régions. Même le nombre 31 dépendait d’une hypothèse cachée (jamais trois cordes concourantes) que l’observation ne montrait pas. Remarquez enfin la « règle de la corde » : une corde qui en croise k ajoute k + 1 régions. C’est un vrai argument de passage d’une étape à la suivante, et c’est lui qui, à la planche 5, permettra de démontrer la bonne formule.

Une récurrence complète : l’inégalité de Bernoulli

Question : à quoi sert chaque hypothèse dans une preuve par récurrence ? L’inégalité de Bernoulli affirme que pour tout réel x ⩾ −1 et tout entier n ⩾ 1, (1 + x)ⁿ ⩾ 1 + nx. Géométriquement, la courbe y = (1 + x)ⁿ reste au-dessus de sa tangente en 0, la droite y = 1 + nx. Déplacez x et n, puis regardez la chaîne d’inégalités qui fait passer de n à n + 1.

Initialisation (n = 1). (1 + x)¹ = 1 + x ⩾ 1 + 1·x : c’est une égalité.

Hérédité. Supposons (1 + x)ⁿ ⩾ 1 + nx. Comme 1 + x ⩾ 0, on peut multiplier les deux membres par 1 + x sans changer le sens : (1 + x)ⁿ⁺¹ ⩾ (1 + x)(1 + nx) = 1 + (n+1)x + nx² ⩾ 1 + (n+1)x, car nx² ⩾ 0.

Bleu : y = (1 + x)ⁿ. Rouge : la tangente en 0, y = 1 + nx. Segment violet : l’écart au point choisi. Bande rosée : x < −1, là où l’hypothèse n’est plus satisfaite.

Exposant n3

Réel x0,50

(1 + x)ⁿ

—

1 + nx

—

L’inégalité au point choisi

—

Chaîne de l’hérédité pour passer de n à n + 1 : A = (1+x)ⁿ⁺¹, B = (1+x)(1+nx), C = 1+(n+1)x

—

Contrôle sur une grille : n = 1 à 30, x de −1 à 2 par pas de 0,001, puis x de −4 à −1 (exclu)

—

Ce que l’on vient de voir. L’hypothèse x ⩾ −1 ne sert qu’à un endroit : multiplier une inégalité par 1 + x ne conserve le sens que si 1 + x ⩾ 0. Pour x = −3 et n = 4, l’inégalité est vraie (16 contre −11), mais la chaîne qui devrait mener au rang 5 casse au premier maillon (A = −32 < B = 22) ; et, de fait, au rang 5 l’inégalité est fausse (−32 contre −14). Pour n = 6 en revanche, elle redevient vraie (64 contre −17), alors que la preuve ne s’applique toujours pas : une récurrence qui échoue ne prouve pas que l’énoncé est faux, elle dit seulement que cette démonstration ne va pas plus loin. Enfin, la grille ne démontre rien : 90 030 vérifications restent des cas particuliers. Seules les deux lignes de la preuve couvrent tous les x ⩾ −1 et tous les n.

L’hérédité seule ne prouve rien : quatre énoncés de divisibilité

Question : « si c’est vrai pour n, c’est vrai pour n + 1 » suffit-il ? Chaque case ci-dessous est un rang n ; elle affiche le reste de u(n) dans la division par m. Verte si le reste est nul (l’énoncé est vrai à ce rang), rosée sinon. Les flèches rouges indiquent que l’hérédité est démontrée. Lancez la propagation : elle part de l’initialisation, si elle est vraie, et suit les flèches.

Énoncé

Nombre de rangs affichés10

En haut, les flèches d’hérédité (rouges si démontrées, grises barrées sinon). Au milieu, le reste de u(n) modulo m. En bas, la valeur de u(n) quand elle est courte, sinon son nombre de chiffres. Contour bleu épais : rang atteint par la récurrence.

—

Initialisation

—

Hérédité : identité de passage vérifiée en entiers exacts, n = 0 à 300

—

Rangs n ⩽ 300 où m divise vraiment u(n)

—

Conclusion permise

—

Ce que l’on vient de voir. Pour « 3 divise 4ⁿ + 1 », l’hérédité est parfaitement juste : si 3 divise 4ⁿ + 1, il divise 4ⁿ⁺¹ + 1 = 4(4ⁿ + 1) − 3. Et pourtant l’énoncé est faux à tous les rangs : le reste vaut toujours 2. Toutes les flèches sont rouges, mais aucun domino ne tombe, faute de premier. C’est exactement ce que dit la phrase « si c’est vrai pour n, c’est vrai pour n + 1 » quand on oublie l’initialisation. À l’inverse, « 3 divise 2ⁿ + 1 » n’a pas d’hérédité d’un rang au suivant, mais elle en a une de deux en deux : la récurrence démontre alors l’énoncé pour les seuls n impairs, et le compteur confirme qu’il est faux pour tous les n pairs.

Récurrence forte : s’appuyer sur tous les rangs précédents

Question : que faire quand P(n + 1) ne découle pas de P(n) seul ? Dans la récurrence forte, on suppose l’énoncé vrai pour tous les rangs de n₀ à n, et l’on en déduit le rang n + 1. Elle n’est pas plus puissante que la récurrence simple (il suffit de l’appliquer à l’énoncé Q(n) : « P(k) est vrai pour tout k de n₀ à n »), mais elle est bien plus commode quand un problème se coupe en morceaux de tailles quelconques.

Chaque casse coupe un seul morceau en deux le long d’une rainure. Dernière casse en rouge, carrés isolés en vert.

Énoncé : pour réduire une tablette de n carrés en carrés isolés, il faut exactement n − 1 casses, quel que soit l’ordre. Preuve par récurrence forte : une tablette de 1 carré demande 0 casse. Une tablette de n carrés se casse d’abord en deux morceaux de a et b carrés, avec a + b = n et a, b < n ; par hypothèse ils demandent a − 1 et b − 1 casses, soit en tout 1 + (a − 1) + (b − 1) = n − 1. On a eu besoin de l’énoncé pour a et pour b, deux rangs inférieurs quelconques, et pas seulement pour n − 1.

Largeur6

Hauteur4

Stratégie

Casses effectuées

—

Morceaux

—

Morceaux − casses (invariant)

—

Contrôle : 3 000 tablettes de 1×1 à 12×12, stratégie et coupes tirées au hasard

—

Énoncé : tout entier n ⩾ 2 est un produit de nombres premiers. Preuve par récurrence forte : si n est premier, c’est fini. Sinon n = a × b avec 2 ⩽ a, b < n, et par hypothèse a et b sont déjà des produits de premiers ; n aussi. L’arbre ci-dessous est exactement cette preuve déroulée : chaque nœud composé s’appuie sur deux nœuds plus petits.

Nœuds bleus : nombres composés, coupés en a × b avec a le plus grand diviseur ⩽ √n. Nœuds verts : nombres premiers, où la récurrence s’arrête.

Entier n360

Décomposition lue sur les feuilles

—

Produit des feuilles − n

—

Profondeur de l’arbre

—

Contrôle : tous les entiers de 2 à 100 000 (feuilles premières, produit égal à n, même décomposition que par un crible indépendant)

calcul en cours…

Ce que l’on vient de voir. Dans les deux cas, le rang n + 1 dépend de rangs antérieurs impossibles à prévoir : les tailles a et b des deux morceaux, les deux facteurs de n. Une récurrence simple, qui ne regarde que le rang précédent, serait coincée. La récurrence forte revient à dire qu’un entier plus petit a toujours déjà été traité, ce qui repose sur une propriété de ℕ : toute partie non vide a un plus petit élément (le bon ordre). Si l’énoncé était faux quelque part, il y aurait un plus petit contre-exemple, et la preuve montre justement qu’il ne peut pas exister.

Deviner avec des cas particuliers, puis démontrer par récurrence

Question : comment les cas particuliers et la récurrence travaillent-ils ensemble ? En pratique, on commence toujours par calculer des exemples : ils suggèrent une formule. Puis la récurrence la confirme ou la réfute. Le premier onglet montre une conjecture née d’un dessin, le second une machine qui devine une formule à partir de k cas, puis la soumet à l’épreuve de l’hérédité.

Le carré de côté 1 + 2 + … + n est pavé d’équerres (gnomons). L’équerre numéro k contient k carrés de côté k, donc une aire k³. Pour k pair, un carré est coupé en deux moitiés, aux deux bouts de l’équerre.

Cas particuliers : 1 = 1², 1 + 8 = 9 = 3², 1 + 8 + 27 = 36 = 6², 1 + 8 + 27 + 64 = 100 = 10². On devine : 1³ + 2³ + … + n³ = (1 + 2 + … + n)².

Initialisation. 1³ = 1 = 1².

Hérédité. Avec T(n) = n(n+1)/2, l’équerre ajoutée a pour aire T(n+1)² − T(n)² = (n+1)²[(n+2)² − n²]/4 = (n+1)²(4n + 4)/4 = (n+1)³. Ajouter le cube suivant, c’est exactement ajouter l’équerre suivante.

1³ + 2³ + … + n³

—

(1 + 2 + … + n)²

—

Aire de la dernière équerre, comptée carreau par carreau

—

Contrôle en entiers exacts, n = 1 à 2 000

—

La machine prend les k premiers cas particuliers d’une suite, construit le tableau des différences successives, et en tire le polynôme de plus petit degré qui passe par ces k valeurs : c’est la conjecture. Elle la soumet ensuite à la récurrence : l’initialisation est vraie par construction, et l’hérédité exige que P(n+1) − P(n) soit égal à la règle de passage Δ(n) de la suite, identiquement en n. Le calcul se fait en fractions exactes.

Suite étudiée

Cas particuliers utilisés k5

—

Points bleus : vraies valeurs pour n = 1 à 12 (cerclés de vert : les k cas fournis à la machine). Courbe orange : la conjecture. Pour Moser, pointillé violet : 2ⁿ⁻¹.

Initialisation P(1) = u(1)

—

Hérédité : P(n+1) − P(n) − Δ(n)

—

Premier rang où la conjecture se trompe

—

Contrôle indépendant

—

Ce que l’on vient de voir. Les cas particuliers servent à deviner, la récurrence à trancher. Avec k = 4 cas, la machine devine pour S₃ un polynôme de degré 3 qui passe par 1, 9, 36, 100 : l’hérédité le rejette aussitôt, par un reste non nul, avant même qu’on ait trouvé un contre-exemple. Avec k = 5 cas, le reste est identiquement nul : la conjecture devient un théorème, (n(n+1)/2)². Pour les régions de Moser, les cinq valeurs 1, 2, 4, 8, 16 sont compatibles avec 2ⁿ⁻¹ et avec un polynôme de degré 4 ; aucun nombre d’exemples ne choisit entre les deux, mais la règle de passage démontrée géométriquement, C(n,3) + n régions de plus à chaque nouveau point, élimine 2ⁿ⁻¹ (dès n = 5, 16 ≠ 15) et démontre le polynôme.

Repères historiques

vers 100Nicomaque de Gérase remarque que les cubes s’obtiennent en groupant les nombres impairs : 1, 3 + 5, 7 + 9 + 11… Cas particuliers observés, sans démonstration générale.

1575Francesco Maurolico, dans ses Arithmeticorum libri duo, démontre que la somme des n premiers impairs vaut n² en passant explicitement d’un rang au suivant : l’une des premières récurrences écrites.

1654Blaise Pascal, dans le Traité du triangle arithmétique, sépare nettement les deux étapes : un premier « lemme » pour la première base, un second pour le passage d’une base à la suivante.

1659Pierre de Fermat décrit sa « descente infinie » : un contre-exemple en fabriquerait un plus petit, ce qui est impossible dans les entiers. C’est la forme contraposée de la récurrence forte.

1838Augustus De Morgan donne au procédé le nom anglais de mathematical induction, pour le distinguer de l’induction des sciences expérimentales.

1888–1889Richard Dedekind puis Giuseppe Peano font de la récurrence un axiome qui définit les entiers naturels eux-mêmes : toute partie de ℕ qui contient 0 et qui est stable par passage au successeur est ℕ tout entier.

1902Henri Poincaré, dans La Science et l’Hypothèse, voit dans le raisonnement par récurrence le raisonnement mathématique par excellence, celui qui permet de franchir l’infini en un nombre fini de mots.

Synthèse

Deviner n’est pas démontrer

Des cas particuliers, même nombreux, ne prouvent rien : 1, 2, 4, 8, 16 annonçaient 32, le cercle donne 31. Ils restent indispensables pour trouver quoi démontrer.

Deux étages, tous deux indispensables

L’initialisation sans hérédité ne dit rien des autres rangs ; l’hérédité sans initialisation ne démarre jamais, comme pour « 3 divise 4ⁿ + 1 ». La conclusion demande les deux.

Un principe, plusieurs formes

Récurrence simple, de deux en deux, forte, descente infinie : toutes reposent sur le fait que ℕ n’a pas de suite infinie décroissante, et que toute partie non vide a un plus petit élément.

Pour aller plus loin

Récurrence et bon ordre. Le principe de récurrence et le principe du bon ordre (toute partie non vide de ℕ a un plus petit élément) sont équivalents. Démontrer par récurrence, c’est montrer que l’ensemble des contre-exemples n’a pas de plus petit élément, donc qu’il est vide.

Récurrence structurelle. Le même schéma s’applique à des objets construits par étapes : arbres, formules logiques, programmes. On vérifie la propriété pour les briques de base, puis on montre que chaque règle de construction la conserve. C’est ainsi qu’on prouve qu’un arbre binaire a une feuille de plus que de nœuds internes.

Récurrence transfinie. Sur les ordinaux, on ajoute une troisième étape : les rangs « limites », qui n’ont pas de prédécesseur, héritent de la propriété de tous les rangs précédents.

Pages voisines du cahier. Le mécanisme des dominos, la somme des entiers, le choix du rang de départ et les tours de Hanoï sont traités dans raisonnement par recurrence ; la récurrence vue comme énoncé sur les parties de ℕ et la descente de Fermat, dans L'arithmetique.