Voir la source de Raisonnement par récurrence

{{Voir homonymes|Récurrence}}
[[Fichier:Dominoeffect.png|vignette|Le raisonnement par récurrence est comme une [[Effet domino|suite de dominos]]. Si la propriété est vraie au rang n<sub>0</sub> (''[[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 [[entier naturel|entiers naturels]]. Le raisonnement par '''récurrence''' consiste à démontrer les points suivants :

* la propriété est satisfaite par un entier ''n''<sub>0</sub> (généralement 0 ou 1) ;
* chaque fois que cette propriété est satisfaite par un certain nombre entier naturel ''n'' ≥ ''n''<sub>0</sub>, 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 à ''n''<sub>0</sub>.

== Présentation ==

Le raisonnement par récurrence établit une propriété importante des entiers naturels : celle d'être construits à partir d'un entier n<sub>0</sub> en itérant le passage au successeur. Dans une [[axiomes de Peano|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 ([[Ensemble bien ordonné|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 [[Relation d'ordre|isomorphe]] à un [[Nombre ordinal|ordinal]]) ; le terme d’'''induction''' est aussi souvent utilisé dans ce contexte. Le raisonnement par récurrence peut se généraliser enfin aux [[relation bien fondée|relations bien fondées]]. Dans certains contextes, en [[logique mathématique]] ou en [[informatique]], pour des structures de nature [[arbre (mathématiques)|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 [[relation de récurrence|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 (historien)|Jean Itard]] en 1961 à propos des ''[[Éléments d'Euclide|Éléments]]'' d'[[Euclide]] : {{Citation|On ne trouvera jamais le leitmotiv moderne un peu pédant : « nous avons vérifié la propriété pour 2, nous avons montré que si elle est vraie pour un nombre, elle est vraie pour son suivant, donc elle est générale » et ceux qui ne voient l'induction complète qu'accompagnée de sa rengaine auront le droit de dire qu'on ne la trouve pas dans les Éléments. Pour nous, nous la voyons dans les prop. 3, 27 et 36, VII, 2, 4 et 13 VIII, 8 et 9 IX<ref>Jean Itard, ''Les livres arithmétiques d'Euclide'', Hermann 1961, cité par {{Harvsp|Rashed|1972}} et {{Harvsp|Acerbi|2000}}.</ref>.}} Ce point de vue n'est cependant pas forcément partagé par les autres historiens<ref>Voir, parmi les références, {{Harvsp|Rashed|1972}} et {{Harvsp|Acerbi|2000}}.</ref>.

=== Le {{s-|XVII|e}} et ensuite ===
[[Image:TrianguloPascal.jpg|vignette|upright=1.5|Le triangle de Pascal extrait de son manuscrit. Par base Pascal entend une diagonale du triangle. Pascal se sert de la géométrie de son triangle pour en énoncer les propriétés. En termes modernes : les coefficients binomiaux sont définis par la relation <math>\binom{n+1}{p+1}=\binom{n}{p+1}+\binom{n}{p}</math> ; la ''conséquence XII'', celle à propos de laquelle Pascal introduit la récurrence, revient à énoncer que pour tout entier ''p'' entre 1 et ''n'', <math>\binom{n}{p}=\frac{n-p+1}{p}\binom{n}{p-1}</math>, ce que Pascal démontre par récurrence sur ''n''. L'étape de récurrence est exposée sur un cas particulier<ref name=TriangleAri>[https://books.google.fr/books?id=KaGl-QaoALMC&pg=PA415&dq=Blaise+Pascal+Trait%C3%A9+du+triangle#PPA420,M1 Traité du triangle arithmétique].</ref>.]]
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 ceci<ref>Pour une discussion précise de ce texte et de ce qu'il peut signifier pour Pascal, voir {{Harvsp|Acerbi|2000}}, introduction et note 13 {{p.|60}}.</ref> :
{{Citation bloc|Quoique cette proposition ait une infinité de cas, j'en donnerai une démonstration bien courte, en supposant deux lemmes.

Le premier, qui est évident de soi-même, que cette proportion se rencontre dans la seconde base; car il est bien visible, que φ est à σ comme 1 est à 1.

Le deuxième, que si cette proportion se trouve dans une base quelconque, elle se trouvera nécessairement dans la base suivante.

D'où il se voit qu'elle est nécessairement dans toutes les bases : car elle est dans la seconde base par le premier lemme ; donc par le second elle est dans la troisième base, donc dans la quatrième, et à l'infini<ref name=TriangleAri/>.}}

Toujours au {{s-|XVII|e}}, il faut mentionner [[Pierre de Fermat]]<ref>D'après Wallis lui-même, voir {{Harvsp|Cajori|1918}}.</ref> et [[Jacques Bernoulli]]<ref>En 1686, ''Acta eruditorum'', d'après {{Harvsp|Cajori|1918}}.</ref> qui critiquent tous deux la « méthode d'induction »<ref>Selon {{Harvsp|Cajori|1918}}, 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. [[Henri Poincaré|Poincaré]]), au moins dans les milieux universitaires.</ref> 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]]<ref name="EuclideIX31">[[Livre IX des Éléments d'Euclide|''Éléments'' d'Euclide, Livre IX]], proposition 31.</ref>. [[Jean Bernoulli|Bernoulli]], lui, propose de démontrer le passage de ''n'' à {{nobr|''n'' + 1,}} soit exactement le raisonnement par récurrence.

Au cours du {{sp-|XVIII|e|et du|XIX|e}}, le raisonnement par récurrence est de plus en plus utilisé pour aboutir finalement à sa formalisation et à son axiomatisation, d'abord partiellement par [[Hermann Günther Grassmann|Grassmann]] en 1861<ref>[[Hermann Günther Grassmann|Grassmann]], ''Lehrbuch der Arithmetik'', 1861</ref>, puis par [[Richard Dedekind]] en 1888 et indépendamment par [[Giuseppe Peano]] en 1889<ref>Peano 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 {{en}} Hubert C. Kennedy, « The mathematical philosophy of Giuseppe Peano », ''Philosophy of Science'', vol. 30, {{n°|3}}, 1963 {{Lire en ligne|url=https://web.archive.org/web/20080407051646/http://home.att.net/~clairnorman/Twelve_Articles.pdf}}.</ref>. 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<ref>{{de}} Richard Dedekind, ''Stetigkeit und irrationale Zahlen'', Brunswick, 1872.</ref>. 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 {{s-|XVII|e}} ===

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 [[Algèbre|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.

{{Harvsp|Cajori|1918}} la décèle dans la [[méthode chakravala]] de [[Bhāskara II]] et dans la [[Théorème d'Euclide sur les nombres premiers|démonstration d'Euclide de l'existence d'une infinité de nombres premiers]]<ref>''Éléments'' d'Euclide, Livre IX, prop. 20. Voir également la citation de Jean Itard {{Supra|Histoire}}, contredit par {{Harvsp|Acerbi|2000|p=72}}.</ref>.

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 {{Harvsp|Rashed|1972}}. Ainsi, vers l'an 1000, le persan [[Al-Karaji]] <small>(953-1029)</small> é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<ref><!---Rashed (1972), p.11 parle de Samawal--->{{Harvsp|Katz|1998|p=255 et 258}}.</ref>, [[Ibn Yahyā al-Maghribī al-Samaw'al|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]] (<small>953-1039)</small> utilise le raisonnement par récurrence pour calculer la somme des cubes puis des puissances quatrièmes des ''n'' premiers entiers naturels{{sfn|Katz|1998|p=256-259}}. 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…)<ref>{{Harvsp|Rabinovitch|1970}} ; {{Harvsp|Katz|1998|p=302-306}}.</ref>.

Pascal, ou Bernoulli étaient déjà considérés au {{s-|XIX|e}} comme les pères du raisonnement par récurrence, mais ensuite, on a beaucoup cité pendant la première moitié du {{s-|XX|e}} le mathématicien italien [[Francesco Maurolico]] <small>(1494-1575)</small> et son ouvrage ''Arithmeticorum libri duo'' (1575)<ref>{{la}} F. Maurolico, ''Arithmeticorum libri duo'', [https://gallica.bnf.fr/ark:/12148/bpt6k83056z/f10 texte original] sur [[Gallica]].</ref>, ceci à la suite d'un article de [[Giovanni Vacca]] de 1909, qui influença [[Moritz Cantor]]<ref>Voir {{harvsp|Bussey|1917}}.</ref> et fut traduit dans d'autres langues, par exemple en français en 1911. Pour démontrer que la [[Preuve_sans_mots#Somme_des_nombres_impairs|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{{sfn|Rashed|1972|p=10}}, 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 {{Harvsp|Freudenthal|1953|texte=Freudenthal de 1953}}{{sfn|Rashed|1972|p=1-2}} 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 plus<ref>Le nom de Maurolico n'apparait pas dans l'index du livre de {{Harvsp|Katz|1998|texte=Katz (1995, 1998)}}, 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 à {{harvsp|Bussey|1917}}.</ref>.

== 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 visualiser<ref name="visualiser une récurrence">[https://www.youtube.com/watch?v=a6AWclssIF4 Principe de récurrence avec des dominos en vidéo].</ref> 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 [[ensemble#Définition d’un ensemble en compréhension|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'')
Alors ''E'' = '''N'''<ref>{{en}} [[Paul Halmos]], ''Naive set theory'', Van Nostrand, trad. J. Gardelle, ''Introduction à la théorie des ensembles'', Mouton, Paris/La Haye, 1970, chap. 12, {{p.|58}}.</ref>.

Bien sûr, l'initialisation peut commencer à un entier ''k'' arbitraire et dans ce cas la propriété n'est démontrée vraie qu'à partir du rang ''k'' :

Si :
* ''P''(''k'') ;
* Pour tout entier ''n'' supérieur ou égal à ''k'', [''P''(''n'') implique ''P''(''n'' + 1)] ;
Alors pour tout entier ''n'' supérieur ou égal à ''k'', ''P''(''n'').

Cette récurrence à partir de ''k'' est une conséquence immédiate de la récurrence à partir de 0 : il suffit de démontrer « ''n'' < ''k'' ou ''P''(''n'') », ou encore « ''P''(''n''+''k'') » si l'on dispose de l'addition, par récurrence sur ''n'' ; chacune de ces propriétés est bien vraie pour tout entier ''n'' si et seulement si la propriété ''P'' est vraie pour tout entier supérieur ou égal à ''k''.

De façon analogue on aura d'autres raisonnements par récurrence, sans avoir besoin de poser à chaque fois un nouveau principe, par exemple, une récurrence sur les entiers pairs (prendre ''P''(2''n'')), etc.

=== Exemple 1 : la somme des ''n'' premiers entiers impairs ===

Les entiers impairs sont les entiers de la forme 2''n'' + 1 (le premier, obtenu pour ''n'' = 0, est 1). On déduit d'une [[identité remarquable]] bien connue que 2''n'' + 1 ajouté au carré de ''n'' donne le carré du nombre suivant :
{{Retrait|''n''{{exp|2}} + 2''n'' + 1 {{=}} (''n'' + 1){{exp|2}} }}
On va donc montrer par récurrence que la somme des ''n'' premiers entiers impairs est égale au carré de ''n'' :
{{Retrait|1 + 3 + … + (2''n'' – 1) {{=}} ''n''{{exp|2}}. }}
Bien que l'écriture précédente puisse laisser entendre que 2''n'' – 1 > 3, on ne le supposera pas<ref>On ne suppose même pas que 2''n'' – 1 ≥ 1, ''i. e.'' que le nombre ''n'' de termes de la somme vaut au moins 1, puisqu'on veut inclure le cas {{nobr|1=''n'' = 0.}} La notation <math>\sum_{1\le k\le n}(2k-1)=n^2</math> inciterait moins à ces présupposés indésirables.</ref>. La [[Somme vide|somme est vide donc nulle]] si ''n'' = 0, réduite à 1 si ''n'' = 1, égale à 1 + 3 si ''n'' = 2{{etc.}}
* initialisation : le cas ''n'' = 0 est celui où la somme est vide, elle est donc bien égale à 0{{exp|2}} ;
* hérédité : raisonnons sur un éventuel entier ''n'', arbitraire, mais pour lequel 1 + 3 + … + (2''n'' – 1) = ''n''{{exp|2}}. Puisque l'entier impair qui suit 2''n'' – 1 est 2''n'' + 1, on en déduit que : {{Retrait|1 + 3 + … + (2''n'' – 1) + (2''n'' + 1) {{=}} ''n''{{exp|2}} + 2''n'' + 1 {{=}} (''n'' + 1){{exp|2}},}}c'est-à-dire que la propriété est héréditaire.

=== Exemple 2 : Identité du binôme de Newton ===
{{Article détaillé|Formule du binôme de Newton}}

<math>(x+y)^n=\sum_{k=0}^n {n \choose k} x^{n-k} y^k.</math>

=== Précautions à prendre ===

* L’initialisation ne doit pas être oubliée. Voici un exemple un peu ad hoc (et que l'on pourrait traiter à l'aide de [[Congruence sur les entiers|congruences modulo]] 7) mais qui illustre bien ceci. On montre facilement que les propriétés « 9{{exp|''n''}} – 2{{exp|''n''}} est un multiple de 7 » et « {{nobr|9{{exp|''n''}} – 2{{exp|''n''+1}}}} est un multiple de 7 » sont toutes deux héréditaires. Cependant, alors que la première est vraie pour tout entier naturel ''n'', la seconde ne l'est pas car elle n’est pas initialisable : en effet, en ''n'' = 0 on a 1 – 2 = –1, qui n'est pas divisible par 7. Pour la première proposition :
** on vérifie que si ''n'' = 0, 9{{exp|0}} – 2{{exp|0}} est bien un multiple de 7 (0 est bien un multiple de 7) ;
** on montre que si 9{{exp|''n''}} – 2{{exp|''n''}} est un multiple de 7, alors 9{{exp|''n''+1}} – 2{{exp|''n''+1}} est un multiple de 7 :{{Retrait|<math>\begin{align}9^{n+1}-2^{n+1}&= 9\times9^n-2\times2^n\\
&=9\times\left(9^n-2^n\right)+9\times2^n-2\times2^n\\
&=9\times\left(9^n-2^n\right)+7\times2^n.\end{align}</math>}}{{Retrait|9{{exp|''n''+1}} – 2{{exp|''n''+1}} est donc somme de deux multiples de 7 ; c’est bien un multiple de 7.}}L'hérédité de la seconde propriété est strictement analogue. Pourtant, cette propriété n'est vraie pour aucun entier puisque 9{{exp|''n''}} – 2{{exp|''n''+1}} est la différence de 9{{exp|''n''}} – 2{{exp|''n''}} (multiple de 7) et de 2{{exp|''n''}} (non divisible par 7).
* L’hérédité doit être démontrée pour tout entier ''n'' ''supérieur ou égal'' au dernier ''n''{{ind|0}} pour lequel la propriété a été démontrée directement (initialisation).
{{Retrait|Si l'on prend, par exemple, la suite <math>u_n = \frac{n^2 - n + 1}{n^2}</math>, on peut observer que cette suite est croissante à partir de ''n'' {{=}} 2 car <math> u_{n+1} - u_n = \frac{n^2 - n - 1}{n^2(n+1)^2} > 0</math>.}}
{{Retrait|Si l'on cherche à démontrer que <math>u_n \geq 1</math> pour tout <math> n \geq 1</math> :}}
{{Retrait|l’initialisation est facile à prouver car <math>u_1 = 1</math> ;|taille=4em}}
{{Retrait|l’hérédité aussi car, la suite étant croissante, si <math>u_n \geq 1</math> alors <math>u_{n+1} \geq 1</math>.|taille=4em}}
{{Retrait|Pourtant cette inégalité est vraie seulement pour ''n'' {{=}} 1. L’hérédité n’a en réalité été prouvée que pour ''n'' supérieur ou égal à 2 et non pour ''n'' supérieur ou égal à 1. }}

== Autres formes de récurrence, énoncés équivalents ==
Plusieurs formes de récurrence, en apparence plus générales que la récurrence ordinaire, s'avèrent équivalentes.
=== Récurrence d’ordre 2 ===

Il peut arriver que, pour l'hérédité, quand il s'agit de démontrer ''P''(''n'' + 1), on ait besoin de supposer la propriété aux deux rangs précédents, c'est-à-dire non seulement pour ''n'', mais aussi pour ''n'' – 1. On est amené à utiliser le principe de récurrence suivant :

Soit ''P''(''n'') une propriété définie sur '''N''', si :
* ''P''(0)
* ''P''(1)
* [''P''(''n'') et ''P''(''n'' + 1)] ⇒ ''P''(''n'' + 2) (pour tout ''n'' ∈ '''N''')
alors ''P''(''n'') pour tout ''n'' ∈ '''N'''.

Cette propriété est en apparence plus forte que la récurrence simple, puisque l'on a une hypothèse supplémentaire à notre disposition, mais lui est en fait équivalente, puisque cela revient à démontrer [''P''(''n'') et ''P''(''n'' + 1)] par récurrence simple. On trouvera par exemple dans l'article [[suite de Fibonacci]] des exemples d'application de ce principe de récurrence.

=== Récurrence forte ===
La récurrence précédente peut être généralisée à plus d'hypothèses, 3, 4{{etc.}} Mais tous ces principes apparaissent comme des cas particuliers du principe de récurrence suivant, parfois appelé ''récurrence forte'', qui permet, pour démontrer la propriété au rang suivant de la supposer vraie pour ''tous'' les rangs inférieurs (pour cette raison, cette forme de récurrence est aussi appelée ''récurrence cumulative''). On a une version plus forte de l’hérédité :

Soit ''P''(''n'') une propriété définie sur '''N''', si :
* ''P''(0)
* [∀''k''≤''n'' ''P''(''k'')] ⇒ ''P''(''n'' + 1) (pour tout ''n'' ∈ '''N''')
alors ''P''(''n'') pour tout entier ''n'' ∈ '''N'''.

L'initialisation reste identique, mais l'hérédité est modifiée. Pour démontrer la propriété au rang ''n'' + 1, on peut supposer la propriété vraie non seulement pour ''n'' mais aussi pour tous les entiers inférieurs à ''n''.

À nouveau cette propriété, en apparence plus forte que la récurrence simple, lui est en fait équivalente. En effet cela revient à démontrer par récurrence simple la propriété « ∀''k''≤''n'' ''P''(''k'') », c'est-à-dire la propriété ''P'' pour tous les entiers inférieurs ou égaux à ''n''. On utilise pour l'équivalence les propriétés qui caractérisent l'ordre sur '''N''', à savoir que pour tout entier naturel ''k'' :
{{Retrait|''k'' ≤ ''n'' + 1 ⇔ (''k'' ≤ ''n'' ou ''k'' {{=}} ''n'' + 1) }}
{{Retrait|''k'' ≤ 0 ⇔ ''k'' {{=}} 0. }}
Cette récurrence peut également se décaler à partir d'un certain rang, exactement comme la récurrence simple.

==== Exemple d'utilisation ====

Pour démontrer que tout entier naturel supérieur ou égal à 2 possède un diviseur [[nombre premier|premier]] (récurrence donc à partir du rang 2).
* On démontre que 2 possède un diviseur premier qui est lui-même
* Soit ''n'' un entier supérieur ou égal à 2, on suppose que tous les entiers ''d'' supérieurs ou égaux à 2 et inférieurs ou égaux à ''n'' possèdent un diviseur premier (hypothèse de récurrence) et l'on cherche à prouver qu’il en est de même pour ''n'' + 1.
{{Retrait|ou bien ''n'' + 1 est premier alors il possède un diviseur premier qui est lui-même}}
{{Retrait|ou bien ''n'' + 1 est composé et il existe un entier ''d'' supérieur ou égal à 2 et inférieur ou égal à ''n'' qui divise ''n'' + 1. Alors, par hypothèse de récurrence, ''d'' possède un diviseur premier, qui est aussi diviseur de ''n'' + 1. }}
Le raisonnement qui est fait pour ''n'' + 1 fonctionne tout aussi bien pour 2 : on voit sur l'exemple qu'il n'est pas vraiment nécessaire de traiter à part l'initialisation, c'est-à-dire que cette démonstration se fait plus élégamment par récurrence bien fondée ou en utilisant le principe du bon ordre (voir ci-dessous).

=== Bon ordre ===
{{Article détaillé|Récurrence transfinie#Ordinal{{!}}Récurrence sur les ordinaux}}
De façon alternative à la récurrence, en particulier la récurrence forte, on peut utiliser le principe suivant :
{{Retrait|Tout sous-ensemble ''non vide'' de '''N''' a un [[plus petit élément]] ('''N''' ''est [[Ensemble bien ordonné|bien ordonné]]''). }}
Par exemple, si l'on reprend l'exemple traité au paragraphe précédent, l'existence pour tout nombre d'un diviseur premier<ref>Qui est aussi l'un des premiers exemples connus du raisonnement assez proche, par descente infinie, voir le [[livre IX des Éléments d'Euclide]], proposition 31.</ref>, on choisit directement ''p'' le plus petit diviseur différent de 1 d'un nombre ''n'' donné supérieur ou égal à 2, qui est le plus petit élément de l'ensemble non vide des diviseurs différents de 1 de ''n''. On montre alors par l'absurde que ''p'' est premier : si ''p'' avait un diviseur strictement inférieur à ''p'' et différent de 1, il diviserait également ''n'', et ''p'' ne serait pas le plus petit diviseur de ''n''.

Cette propriété est une propriété de la [[relation d'ordre]] sur '''N'''. Un tel ordre est appelé [[bon ordre]], et l'on dit que '''N''' est bien ordonné.

{{Retrait|''La propriété de récurrence se déduit de celle de bon ordre, et du fait que tout entier est soit'' 0, ''soit un successeur'' (''de la forme'' ''n'' + 1). }}

En effet, pour une propriété ''P'' héréditaire (''P''(''n'') ⇒ ''P''(''n'' + 1)) et vérifiée en 0, il suffit de considérer le minimum de l'ensemble des entiers ne vérifiant pas celle-ci. Il existe dès que cet ensemble est non vide. Grâce à l'initialisation, on sait que ce minimum n'est pas 0 . Grâce à l'hérédité, on sait que ce minimum n'est pas le successeur ''n'' + 1 d'un entier ''n'' qui vérifierait la propriété ''P''. Par conséquent, l'ensemble des entiers ne vérifiant pas ''P'' ne possède pas de minimum, il est donc vide : tout entier vérifie ''P''.

Réciproquement,
{{Retrait|''la propriété de bon ordre se déduit de la propriété de récurrence (et des propriétés de l'ordre)''. }}
La contraposée de la propriété de bon ordre se déduit en effet directement de la récurrence forte (en utilisant les propriétés caractérisant l'ordre sur '''N'''). On suppose qu'un ensemble E ''d'entiers,n'' n'a pas de plus petit élément, et l'on doit montrer que E est vide, soit pour tout entier ''n'', ''n'' ∉ E :
* 0 ∉ ''E'' (car sinon 0 serait le plus petit élément de ''E'') ;
* on suppose pour tout entier ''k'' ≤ ''n'', ''k'' ∉ E. Alors ''n'' + 1 ∉ E, car sinon il serait le plus petit élément de E.

Une fois admises certaines propriétés des entiers naturels (en particulier que tout entier est 0 ou le successeur d'un autre entier), on a donc équivalence entre principe de récurrence et propriété de bon ordre.

=== Principe de descente infinie de Fermat ===
{{Article détaillé|Méthode de descente infinie}}
Un autre principe proche de la récurrence, en particulier de la récurrence forte, est le principe de [[descente infinie]] illustré par [[Pierre de Fermat]] :
{{Retrait|il n'existe pas de suite infinie strictement décroissante d'entiers naturels. }}
Fermat démontre ainsi par l'absurde des résultats d'inexistence de solutions à certaines [[équation diophantienne|équations diophantiennes]], en construisant à partir d'une solution supposée une autre solution strictement plus petite.

C'est une conséquence directe de la propriété de [[bon ordre]], si telle suite existait, l'ensemble non vide de ses valeurs n'aurait pas de minimum. Le principe de descente infinie est directement lié à la notion de [[relation bien fondée]], abordée dans le paragraphe suivant, dont il fournit une caractérisation.

=== Récurrence bien fondée ===
{{Article détaillé|Récurrence bien fondée}}
On peut réénoncer la récurrence forte en utilisant la seule relation d'ordre, et les deux hypothèses de récurrence peuvent alors se rassembler en une seule.

Soit ''P''(''n'') une propriété définie sur '''N''',
{{Retrait|si [∀''k'' < ''n'' ''P''(''k'')] ⇒ ''P''(''n'') (pour tout ''n'' ∈ '''N''')}}
{{Retrait|alors ''P''(''n'') pour tout ''n'' ∈ '''N'''.}}

Dans le cas où ''n'' = 0, l'hypothèse est vraie par vacuité de l'ensemble des ''k'' < ''0'', ainsi la quantification est vraie et l'assertion revient à ''P''(''0''). Donc quand on prend pour < l'ordre naturel sur les entiers<ref>Un autre ordre possible pourrait être l'ordre ''k'' | ''n'' à savoir ''k'' divise ''n''.</ref>, on distingue suivant que ''n'' = 0 ou ''n'' est un « successeur », c'est-à-dire ''n'' est de la forme ''m'' + 1, on retrouve exactement la propriété de récurrence forte ci-dessus.

Cette forme du raisonnement par récurrence ne fait plus référence à la constante 0 et à l'opération successeur des entiers. Elle se généralise directement à n'importe quel [[ordre bien fondé]] non nécessairement [[ordre total|total]] (et même à n'importe quelle [[relation bien fondée]]).

En effet, dire que la relation d'[[ordre strict]] sur '''N''' est bien fondée signifie que
{{Retrait|toute partie non vide de '''N''' possède un [[élément minimal]]}}
(donc ici [[élément minimum|minimum]], puisque l'ordre sur '''N''' est total), or on démontre aisément ({{cf.}} article détaillé) que cette propriété équivaut à la récurrence bien fondée. La démonstration est en fait essentiellement celle donnée ci-dessus entre récurrence et bon ordre via la récurrence forte. Mais comme il existe des bons ordres qui ne sont pas isomorphes à l'ordre usuel sur '''N''', on a forcément utilisé au passage une propriété spécifique des entiers, en l'occurrence le fait que tout entier non nul est le successeur d'un autre entier. Cette dernière propriété est d'ailleurs une conséquence de la propriété de récurrence simple (le cas très particulier où l'on n'utilise pas l'hypothèse de récurrence). Elle n'est pas nécessairement vraie dans les ensembles bien ordonnés.

=== Un principe de récurrence alternatif ===

Dans son opuscule sur la [[fonction gamma]]<ref>{{en}} Emil Artin, ''The Gamma Function'', Holt, Rinehart and Winston, 1964, page 5, (1.8) {{Lire en ligne|url=http://inis.jinr.ru/sl/vol1/UH/_Ready/Mathematics/Advanced%20calculus/Artin%20E.%20The%20Gamma%20function%20(1931)(L)(23s).pdf}}, « {{Lang|en|[[Fonction convexe|Convex Functions]]}} », {{p.|5}}.</ref>, [[Emil Artin]] utilise, pour [[Fonction convexe#Possibilité de n'utiliser que des milieux|étendre à tous les isobarycentres l'inégalité de convexité pour les milieux]], un principe de récurrence qui s'adapte bien au cas où la propriété se démontre facilement pour les [[Puissance de deux|puissances de 2]]. Ce principe<ref>[[Augustin Cauchy]] [https://gallica.bnf.fr/ark:/12148/bpt6k90195m/f380.item.zoom ''Cours d'analyse''] p. 376, cité par [[Pólya]] et [[Gábor Szegő|Szegő]], ''Problems and Theorems in Analysis'', vol I, Springer-Verlag, 1998, [https://books.google.fr/books?id=b9l2NqGEFzgC&pg=PA64 {{p.|64}}].</ref> avait déjà été utilisé par [[Augustin Louis Cauchy|Cauchy]] pour démontrer l'[[inégalité arithmético-géométrique]] <math>(x_1x_2\dots x_n)^{1/n}\le(x_1+x_2+\cdots+x_n)/n</math>. Son énoncé est le suivant :

Soit ''P''(''n'') une propriété définie sur '''N''' :
* si ''P''(1),
* si pour tout ''n'' ∈ '''N''', ''P''(''n'') ⇒ ''P''(2''n''),
* et si pour tout ''n'' ∈ '''N''', ''P''(''n'' + 1) ⇒ ''P''(''n''),
alors, pour tout entier ''n'' ∈ '''N''', ''P''(''n'').

L'originalité de cette méthode repose sur un principe de récurrence ''à rebours'' : on ne prouve plus une propriété de ''n'' à ''n'' + 1 mais de ''n'' + 1 à ''n'', en y adjoignant que si la propriété est vraie d'un entier alors elle est vraie pour un autre entier strictement plus grand, ce qui donne une preuve de la propriété sur tous les entiers « en zigzag ».

== Généralisations ==
{{article détaillé|récurrence transfinie|nombre ordinal|relation bien fondée|induction structurelle}}
Le raisonnement par récurrence se généralise naturellement, sous la forme de la récurrence bien fondée indiquée au paragraphe [[#Récurrence bien fondée|récurrence bien fondée]], aux ensembles sur lesquels on peut définir un [[bon ordre]], isomorphe alors à un ordinal, ou simplement une [[relation bien fondée]].

== Justification du principe de récurrence ==

Le texte de [[Blaise Pascal]] cité plus haut, premier texte où le raisonnement par récurrence apparaît de façon tout à fait explicite, donne une justification intuitive très naturelle de celui-ci : le fait qu'il permette de construire une démonstration directe pour n'importe quel entier, justification toujours employée de nos jours<ref>Par exemple Weis et Leroy, ''Le langage CAML'', InterEditions, 1993, p. 54 : {{Citation|Ce principe est en fait évident : les deux propriétés demandées par le principe de récurrence permettent facilement de démontrer la propriété P pour toute valeur entière. Par exemple, supposons que P vérifie les deux propriétés et qu’on veuille démontrer que P est vraie pour 2. Puisque P est vraie pour 0, elle est vraie pour son successeur 1. Mais puisque P est vraie pour 1, elle est vraie pour son successeur, donc elle est vraie pour 2. Il est clair que ce raisonnement se poursuit sans problème pour tout nombre entier fixé à l’avance.}}</ref>. Cependant cette justification ne peut constituer une démonstration de la validité du principe de récurrence. Pour démontrer P(''n'') pour tout entier ''n'', il faudrait écrire '''toutes''' les implications entre P(''n'') et P(''n'' + 1) à partir de P(0), et cela nécessiterait une infinité d’implications. Comme une [[Démonstration (logique et mathématique)|démonstration]] est finie, une telle démonstration ne vaudra donc que pour un entier ''n'' fixé à l'avance. Les deux hypothèses du principe de récurrence permettent théoriquement d'écrire « mécaniquement » une démonstration pour un entier arbitrairement grand, mais non pour tous les entiers.

Le principe de récurrence est donc bien une propriété des entiers naturels, admis en tant qu'[[axiome]] (Dedekind 1888), ou bien démontré dans le cadre d'une théorie plus puissante comme la [[théorie des ensembles]]<ref>{{Ouvrage|auteur1=[[Serge Lang]]|titre=Structures algébriques|éditeur=interéditions|année=1976|passage=p.2|isbn=}}</ref>. Il permet alors de « rassembler » sous la forme d'une seule démonstration finie, cette infinité de démonstrations, une pour chaque entier.

Pour autant l'axiomatisation a-t-elle entièrement capturé l'intuition ? On déduit très directement des [[théorèmes d'incomplétude de Gödel]] (1931) que non. En effet, pour toute [[théorie axiomatique|axiomatisation raisonnable]], par exemple la théorie des ensembles [[ZFC]], chacun de ces deux théorèmes fournit une propriété P des entiers qui s'exprime dans le langage de la théorie, et qui est démontrable pour n'importe quel entier fixé à l'avance, mais pourtant on ne peut démontrer l'énoncé (formalisé dans la théorie) « pour tout entier naturel P(''n'') », par récurrence ou tout autre moyen disponible par l'axiomatisation.

=== Le principe de récurrence et l'ω-incohérence ===
Ainsi, les hypothèses ''P''(0) et ''P'' héréditaire : ∀''n'' [''P''(''n'') ⇒ ''P''(''n'' + 1)] permettent de montrer que, pour tout entier ''n'' donné, on a <math>\vdash P(n)</math> (où le symbole <math>\vdash</math> indique qu'il existe une démonstration de la proposition énoncée). Mais ces hypothèses seules ne permettent pas d'affirmer <math>\vdash \forall n, P(n)</math>, qui est beaucoup plus fort. C'est le principe de récurrence qui le permet.

En effet on peut avoir une théorie T, '''cohérente''', telle que :
* 1/ Pour tout entier ''n'', <math> {\rm T} \vdash P(n)</math>, (donc <math>{\rm T} \vdash P(0)</math>, <math>{\rm T} \vdash P(1)</math>, <math> {\rm T} \vdash P(2)</math>, <math>{\rm T} \vdash P(3)</math>, ...),
Sans que pourtant on ait :
* 2/ <math>{\rm T} \vdash \forall n, P(n)</math>.

Ceci peut se concevoir aisément par un exemple<ref>On connait des exemples de ce type, plus techniques que celui qui suit, mais non hypothétiques : voir le [[théorème de Goodstein]].</ref> :
On ignore actuellement si la [[conjecture de Goldbach]] disant que tout entier pair > 2 est somme de 2 nombres premiers est un énoncé :
* indécidable de la [[Axiomes de Peano|théorie arithmétique]], notée ''AP'', mais
* effectivement vrai (et donc potentiellement démontrable dans une théorie toujours [[Correction arithmétique|arithmétiquement correcte]] mais plus forte, telle que, présume-t-on, la [[théorie des ensembles]] usuelle).
{{Article détaillé|théorème d'incomplétude}}
Si tel est le cas, en prenant pour P(''n''), « 2''n'' + 4 est somme de 2 nombres premiers », on aurait, pour tout entier ''n'' :
* <math>{\rm AP} \vdash P(n)</math> car pour tout nombre pair donné, on pourrait prouver en un nombre fini d'étapes, dans AP qu'il est somme de 2 nombres premiers s'il l'est. Il suffirait pour cela de calculer les sommes des couples de nombres premiers inférieurs à ''n'' et de les comparer à ''n''.

Mais pas :
* <math>{\rm AP} \vdash \forall n, P(n)</math>, dans le cas où la conjecture de Goldbach serait indécidable dans AP.

On peut même avoir une théorie T, '''cohérente''', telle que :
* 1/ Pour tout entier ''n'', <math>{\rm T} \vdash P(n)</math>, et :
* 3/ <math>{\rm T} \vdash {\rm non}(\forall n, P(n))</math>.
Une telle théorie est dite '''simplement cohérente''' et '''ω-incohérente''' (lire ''omega-incohérente'')<ref>Stephen C. Kleene, ''Logique Mathématique'', éd. Jacques Gabay, 1971, p. 281.</ref>.

Ceci se conçoit toujours aisément en reprenant l'exemple ci-dessus :
* Si la proposition "∀''n'' P(''n'')" (ici, la conjecture de Goldbach) est indécidable dans notre théorie (ici, AP), l'adjonction de "non [∀''n'' P(''n'')]" aux axiomes de la théorie 1/ la laisse cohérente si elle l'était et préserve les théorèmes de T. Par ailleurs on a évidemment :
* <math>{\rm T} \cup \{{\rm non} (\forall n, P(n))\} \vdash {\rm non}(\forall n, P(n))</math>
et en remplaçant dans le paragraphe précédent ''T'' par <math>{\rm T'} = {\rm T} \cup \{{\rm non} (\forall n, P(n))\}</math>, on a le résultat attendu.

Ainsi, il ne suffit pas de démontrer que pour tout ''n'', P(''n'') [soit P(0), P(1), P(2), ...] pour démontrer ∀''n'' P(''n''), comme arrive à le faire le principe de récurrence.

Une théorie dans laquelle pour tout prédicat ''P'',
{{Retrait|pour tout ''n'', <math>{\rm T} \vdash P(n)</math> implique <math>T \vdash \forall n P(n)</math>}}
est dite ω-cohérente<ref>Cette notion a été introduite par [[Gödel]] dans sa preuve initiale des théorèmes d'incomplétude qui supposait AP ω-cohérente. Plus tard Rosser a démontré ce même théorème en ne supposant que la seule cohérence de AP.</ref>.

== Articles connexes ==
* [[Analyse non standard]], en particulier la [[Analyse non standard#Les entiers|section sur les entiers]]
* [[Induction structurelle]]
* [[Logique et raisonnement mathématique]]

== Notes ==
{{Références|colonnes=2}}

== Bibliographie ==

Plusieurs des articles historiques spécialisés (Acerbi, Rashed…) commencent par un panorama plus général.
*{{Article|lang=en|auteur=Fabio Acerbi|titre=Plato: Parmenides 149a7-c3. A proof by complete induction?|revue=[[Archive for History of Exact Sciences|Arch. Hist. Exact Sci.]]|vol=55|date=2000|p.=57-76|url=https://web.archive.org/web/20061126003539/http://stl.recherche.univ-lille3.fr/sitespersonnels/acerbi/acerbipub1.pdf}}
* {{Article|lang=en|auteur=W. H. Bussey|titre=The origin of mathematical induction|revue=[[The American Mathematical Monthly|Amer. Math. Monthly]]|vol=24|numéro=5|date=1917|p.=199-207|url=https://archive.org/details/jstor-2974308}}
*{{Article|lang=en|auteur=[[Florian Cajori]]|titre=Origin of the name mathematical induction|revue=Amer. Math. Monthly|vol=25|numéro=5|date=1918|p.=197-201|jstor=2972638}}
* {{de}} [[Richard Dedekind]], ''Was sind und was sollen die Zahlen?'' [« Que sont et que doivent être les nombres ? »], Brunswick, 1888
*{{Article|lang=de|auteur=[[Hans Freudenthal]]|titre=Zur Geschichte der vollständigen Induction|revue=Arch. Hist. Exact Sci.|vol=6|date=1953|p.=17-37}}
* {{Ouvrage|lang=en|auteur=[[Victor J. Katz]]|titre=A History of Mathematics: An Introduction|numéro d'édition=2|date=1998|année première édition=1995|éditeur=Addison-Wesley|isbn=0-321-01618-1}}
* {{la}} [[Giuseppe Peano]], ''Arithmetices principia, nova methodo exposita'' (« Les principes de l'arithmétique, nouvelle méthode d'exposition »), Bocca, Turin, 1889, rep. ''Opera Scelte'', vol II, éd. Cremonese, Rome, 1958 ; traduit en anglais (partiellement) dans [[Jean van Heijenoort]], ''From Frege to Gödel: A Source Book in Mathematical Logic''
* {{Article|lang=en|auteur=Nachum L. Rabinovitch|titre=Rabi Levi Ben Gershon and the origins of mathematical induction|revue=Arch. Hist. Exact Sci.|vol=6|date=1970|p.=237-248|doi=10.1007/BF00327237}}
* {{article|auteur=[[Roshdi Rashed]]|titre= L'induction mathématique : al-Karajī, as-Samaw'al|périodique=Arch. Hist. Exact Sci.|volume= 9|numéro=1|année= 1972|passage= 1-12|doi=10.1007/BF00348537}}
* {{en}} [[Giovanni Vacca]], « Maurolycus, the first discoverer of the principle of mathematical induction », ''[[Bulletin of the American Mathematical Society|Bull. Amer. Math. Soc.]]'', vol. 16, 1909, {{p.}}70-73 {{Lire en ligne|url=http://www.ams.org/bull/1909-16-02/S0002-9904-1909-01860-9}} ; trad. « Sur le principe d'induction mathématique », ''Revue de métaphysique et de morale'', vol. 19, 1911, {{p.}}30-33, [https://gallica.bnf.fr/ark:/12148/bpt6k111193 lire en ligne sur Gallica].{{Commentaire biblio|L'article de Vacca a son importance dans le développement de l'histoire de la récurrence, mais n'est plus considéré comme une référence fiable sur Maurolico, cf. {{Harvsp|Rashed|1972}}, introduction ; voir plutôt {{harvsp|Bussey|1917}} et {{Harvsp|Freudenthal|1953}}.}}
* {{en}} Mohamed Yadegari, ''« The Use of Mathematical Induction by Abu Kamil Shuja' Ibn Aslam (850-930) »'', ''[[Isis (revue)|Isis]]'', vol. 69, {{n°|2}}, 1978, {{p.}}259-262, {{JSTOR|230435}}

{{Portail|mathématiques}}

[[Catégorie:Méthode de démonstration]]