vignette|Le raisonnement par récurrence est comme une suite de dominos. Si la propriété est vraie au rang n0 (i. e. le premier domino de numéro 0 tombe) et si sa véracité au rang n implique celle au rang n + 1 (i. e. la chute du domino numéro n fait tomber le domino numéro n + 1) alors la propriété est vraie pour tout entier (i. e. tous les dominos tombent). En mathématiques, le raisonnement par récurrence (ou par induction, ou induction complète) est une forme de raisonnement visant à démontrer une propriété portant sur tous les entiers naturels. Le raisonnement par récurrence consiste à démontrer les points suivants :
la propriété est satisfaite par un entier n0 (généralement 0 ou 1) ; chaque fois que cette propriété est satisfaite par un certain nombre entier naturel n ≥ n0, elle est également satisfaite par son successeur, c'est-à-dire par le nombre entier n + 1.
Une fois cela établi, on en conclut que cette propriété est vraie pour tous les nombres entiers naturels supérieurs ou égaux à n0.
Présentation
Le raisonnement par récurrence établit une propriété importante des entiers naturels : celle d'être construits à partir d'un entier n0 en itérant le passage au successeur. Dans une présentation axiomatique des entiers naturels, il est directement formalisé par un axiome. Moyennant certaines propriétés des entiers naturels, il est équivalent à d'autres propriétés de ceux-ci, en particulier l'existence d'un minimum à tout ensemble non vide (bon ordre), ce qui permet donc une axiomatisation alternative reposant sur cette propriété.
Certaines formes de ce raisonnement se généralisent d'ailleurs naturellement à tous les bons ordres infinis (pas seulement celui sur les entiers naturels), on parle alors de récurrence transfinie, ou de récurrence ordinale (tout bon ordre est isomorphe à un ordinal) ; le terme d’induction est aussi souvent utilisé dans ce contexte. Le raisonnement par récurrence peut se généraliser enfin aux relations bien fondées. Dans certains contextes, en logique mathématique ou en informatique, pour des structures de nature arborescente ou ayant trait aux termes du langage formel sous-jacent, on parle de récurrence ou induction structurelle.
On parle communément de récurrence dans un contexte lié mais différent, celui des définitions par récurrence de suites (ou d'opérations) à argument entier. Si l'unicité de telles suites se démontre bien par récurrence, leur existence, qui est le plus souvent tacitement admise dans le secondaire, voire les premières années universitaires, repose sur un principe différent.
Histoire L'histoire des débuts du raisonnement par récurrence peut prêter à interprétation, suivant ce que l'on accepte d'identifier comme tel. Si l'on regarde les choses d'assez loin, on peut déclarer, comme Jean Itard en 1961 à propos des Éléments d'Euclide : Ce point de vue n'est cependant pas forcément partagé par les autres historiensVoir, parmi les références, et ..
Le et ensuite
On trouve dans le Traité du triangle arithmétique de Blaise Pascal, écrit en 1654 mais publié en 1665, ce qui est généralement considéré comme la première utilisation tout à fait explicite du raisonnement par récurrence. En particulier, même si Pascal utilise parfois dans son traité des formes moins abouties, il écrit ceciPour une discussion précise de ce texte et de ce qu'il peut signifier pour Pascal, voir , introduction et note 13 . :
Toujours au , il faut mentionner Pierre de FermatD'après Wallis lui-même, voir . et Jacques BernoulliEn 1686, Acta eruditorum, d'après . qui critiquent tous deux la « méthode d'induction »Selon , Wallis est le premier à parler d'induction dans ce contexte. On utilise parfois induction mathématique, induction complète, ou plus récemment simplement induction pour récurrence. Ces termes, plus exactement leurs traductions directes sont utilisés internationalement (allemand, anglais, ...), mais aussi en français depuis fort longtemps (par ex. Poincaré), au moins dans les milieux universitaires. de John Wallis, appelée depuis induction incomplète, qui correspond grossièrement à une démonstration pour les premiers entiers et « ainsi de suite ». Fermat promeut par ailleurs la méthode de descente infinie, liée elle-même à la récurrence (voir ci-dessous). Il est le premier à l'identifier et la nommer mais celle-ci est déjà utilisée, là sans ambiguïté aucune, par EuclideÉléments d'Euclide, Livre IX, proposition 31.. Bernoulli, lui, propose de démontrer le passage de n à soit exactement le raisonnement par récurrence.
Au cours du , le raisonnement par récurrence est de plus en plus utilisé pour aboutir finalement à sa formalisation et à son axiomatisation, d'abord partiellement par Grassmann en 1861Grassmann, Lehrbuch der Arithmetik, 1861, puis par Richard Dedekind en 1888 et indépendamment par Giuseppe Peano en 1889Peano cite Dedekind dans sa préface, mais il a manifestement pris connaissance trop tard de l'ouvrage de Dedekind pour l'utiliser dans son article, voir Hubert C. Kennedy, « The mathematical philosophy of Giuseppe Peano », Philosophy of Science, vol. 30, , 1963 .. Pour Dedekind il s'agit d'achever l'arithmétisation des réels, en donnant un cadre formel permettant de développer la méthode des coupures publiée en 1872 Richard Dedekind, Stetigkeit und irrationale Zahlen, Brunswick, 1872.. Pour Peano ce sont les prémisses de son très ambitieux projet de formalisation des mathématiques (voir Formulaire de mathématiques). Dans les deux cas la récurrence n'est plus simplement un principe de démonstration reposant sur l'intuition, mais un axiome formalisant une propriété des entiers naturels.
Avant le
Que Pascal soit ou non l'inventeur du raisonnement par récurrence, on ne peut négliger ses nombreux précurseurs.
Les choses se compliquent du fait de l'absence d'un langage algébrique moderne. Certains résultats ne peuvent parfois pas même être énoncés en toute généralité, et le sont donc pour des entiers donnés, alors que les idées essentielles pour la démonstration du résultat général (passage de n à n + 1) sont présentes.
la décèle dans la méthode chakravala de Bhāskara II et dans la démonstration d'Euclide de l'existence d'une infinité de nombres premiersÉléments d'Euclide, Livre IX, prop. 20. Voir également la citation de Jean Itard , contredit par ..
On a découvert depuis les années 1970 plusieurs formes de raisonnement par récurrence dans les mathématiques du monde arabo-islamique, voir . Ainsi, vers l'an 1000, le persan Al-Karaji (953-1029) établit la formule du binôme de Newton (en fait il n'a pas les notations qui lui permettraient de l'énoncer dans le cas général, mais les méthodes fonctionnent pour un entier arbitraire). Il calcule également la somme des cubes des n premiers entiers naturels., al-Samaw'al poursuit ses travaux. Ces résultats utilisent bien des formes « archaïques » de définition et de raisonnement par récurrence (comme la régression, on part d'un entier donné choisi arbitrairement, et par un procédé manifestement général, en passant de n à n – 1, on se ramène au cas initial). À peu près à la même époque, Alhazen (953-1039) utilise le raisonnement par récurrence pour calculer la somme des cubes puis des puissances quatrièmes des n premiers entiers naturels. Bien qu'il ne mentionne même pas la possibilité d'aller au-delà de la puissance 4, sa méthode, itérative, le permettrait.
Durant le Moyen Âge européen, le philosophe et mathématicien juif languedocien Levi ben Gershom (1288-1344), dit Gersonide, fait un usage systématique de la régression pour établir des résultats de combinatoire (somme des cubes, nombre de permutations…) ; ..
Pascal, ou Bernoulli étaient déjà considérés au comme les pères du raisonnement par récurrence, mais ensuite, on a beaucoup cité pendant la première moitié du le mathématicien italien Francesco Maurolico (1494-1575) et son ouvrage Arithmeticorum libri duo (1575) F. Maurolico, Arithmeticorum libri duo, texte original sur Gallica., ceci à la suite d'un article de Giovanni Vacca de 1909, qui influença Moritz CantorVoir . et fut traduit dans d'autres langues, par exemple en français en 1911. Pour démontrer que la somme des n premiers entiers impairs est un carré parfait, Maurolico utilise une proposition (prop. 13) qui permet le passage du cas n au cas n + 1, énonce la propriété générale (prop. 15), et en fait la démonstration pour n=1, 2, 3, 4, 5 grâce à la prop. 13, tout en concluant qu'il pourrait poursuivre ainsi jusqu'à l'infini. Selon Rashed et Freudenthal, il s'agirait d'une utilisation archaïque du raisonnement sans énonciation d'un principe général qui serait utilisable de manière systématique. D'autre part il apparaît, d'après la correspondance de Pascal, que celui-ci a lu Maurolico.
L'article de montrant que Maurolico utilise dans son livre très peu de raisonnements de type récurrence (sous quelque forme que ce soit), et d'autre part, les découvertes de travaux antérieurs de Al-Karaji, ben Gershom et autres relativisent fortement son apport, ceci au point que les ouvrages généralistes d'histoire des mathématiques ne le mentionnent plusLe nom de Maurolico n'apparait pas dans l'index du livre de , qui s'intéresse pourtant à plusieurs reprises à la récurrence. De façon symptomatique, N. Bourbaki, dans l’édition de 1960 des Éléments d'histoire des mathématiques, cite p. 38 Maurolico, et remplace purement et simplement son nom par celui de Pascal dans son édition de 1969, en gardant d'ailleurs la même référence à ..
Récurrence simple sur les entiers Pour démontrer une propriété portant sur tous les entiers naturels, comme la formule du binôme de Newton, on peut utiliser un raisonnement par récurrence. Notons la propriété en question P(n) pour indiquer la dépendance en l'entier n. On peut alors l'obtenir pour tout entier n en démontrant ces deux assertions : P(0) (0 vérifie la propriété) : c'est l’initialisation (ou la base) de la récurrence ; Pour tout entier n, (P(n) ⇒ P(n + 1)) : c'est l’hérédité (on dit que P est héréditaire). On dit alors que la propriété P s'en déduit par récurrence pour tout entier n. On précise parfois « récurrence simple », quand il est nécessaire de distinguer ce raisonnement d'autres formes de récurrence (voir la suite).
Une manière facile de visualiserPrincipe de récurrence avec des dominos en vidéo. un raisonnement par récurrence consiste à faire l'analogie avec le jeu de la chute des dominos. On considère une suite infinie de dominos dont chacun porte un numéro (0,1,2,3,...) et l'on cherche des conditions simples pour que tous les dominos chutent. Toute personne qui aura déjà joué à ce jeu comprendra que pour que tous les dominos chutent il suffit que le premier domino (celui numéroté 0) tombe, et que la chute du domino n entraîne la chute du domino n + 1. Si l'on note alors P(n) la propriété « le domino n tombe », alors la chute du domino 0 correspond à l'initialisation précitée, et le fait que la chute du domino n entraîne la chute du domino n + 1 correspond à l'hérédité précitée.
Le raisonnement par récurrence est une propriété fondamentale des entiers naturels, et c'est le principal des axiomes de Peano. Une axiomatique est, en quelque sorte une définition implicite, dans ce cas une définition implicite des entiers naturels. Dans certains contextes, comme en théorie des ensembles, on déduit directement la récurrence de la définition, explicite cette fois, de l'ensemble des entiers naturels.
La récurrence peut aussi s'exprimer de façon ensembliste : il s'agit juste d'une variation sur la définition d'un ensemble en compréhension. On associe à une propriété P l'ensemble E des entiers naturels la vérifiant, et à un ensemble d'entiers naturels E la propriété d'appartenance associée. La récurrence se réénonce alors de façon équivalente ainsi :
Soit E un sous-ensemble de N, si : 0 appartient à E Pour tout entier naturel n, (n appartient à E implique n + 1 appartient à E)