Raisonnement Par Récurrence

Raisonnement Par Récurrence

Raisonnement par récurrence

En mathématiques, le raisonnement par récurrence 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 :

  • Une propriété est satisfaite par l'entier 0 ;
  • Si cette propriété est satisfaite par un certain nombre entier naturel n, alors elle doit être satisfaite par son successeur, c'est-à-dire, le nombre entier n+1.

Une fois cela établi, on en déduit cette propriété pour tous les nombres entiers naturels.

Sommaire

Présentation

Le raisonnement par récurrence établit une propriété importante liée à la structure des entiers naturels : celle d'être construits à partir de 0 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, 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, 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 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 acccepte d'identifier comme tel. Si on regarde les choses d'assez loin on peut déclarer comme Jean Itard en 1961 à propos des éléments d'Euclide 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 [1]. Ce point de vue n'est cependant pas forcément partagé des autres historiens[2].

Le XVIIe siècle et ensuite

Le triangle de Pascal extrait de son manuscript. 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 binômiaux sont définis par la relation {}^{\binom{n+1}{p+1}=\binom{n}{p+1}+\binom{n}{p}} ; la conséquence XII, celle à propos de laquelle Pascal introduit la récurrence, revient à énoncer que pour tout entier p entre 1 et n, {}^{\binom{n}{p}=\frac{n-p+1}{p}\binom{n}{p-1}}, ce que Pascal démontre par récurrence sur n. L'étape de récurrence est exposée sur un cas particulier[3].

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 :

Quoique cette proposition ait une infinité de cas, j'en donnerai une démonstration bien courte, en supposant 2 lemmes.
  • Le 1, 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 2, 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[4].

Toujours au XVIIe siècle, il faut mentionner Pierre de Fermat[5] et Jacob Bernoulli[6] qui critiquent tous deux la méthode d'induction[7] 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 à la récurrence (voir ci-dessous), et qu'il est le premier à identifier et nommer mais qui est déjà utilisée, là sans ambiguïté aucune, par Euclide[8]. Mais Bernoulli propose de démontrer plutôt le passage de n à n+1, c'est-à-dire exactement le raisonnement par récurrence.

Au cours du XVIIIe et du XIXe siècle, 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 1861[9], puis par Richard Dedekind en 1888 et indépendamment par Giuseppe Peano en 1889[10]. 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[11]. 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 XVIIe siècle

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.

Florian Cajori (1918) la décèle dans la méthode cyclique de Bhaskara et dans la démonstration d'Euclide de l'existence d'une infinité de nombres premiers[12].

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 Rashed (1972). 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 permettrait 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[13], 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, Ibn al-Haytham (953-1039) utilise le raisonnement par récurrence pour calculer la somme des cubes puis des puissances quatrièmes des n premiers entiers naturels[14]. 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…)[15].

Pascal, ou Bernoulli étaient déjà considérés au XIXe siècle comme les pères du raisonnement par récurrence, mais ensuite, on a beaucoup cité pendant la première moitié du XXe siècle le mathématicien italien Francesco Maurolico (1494-1575) et son ouvrage Arithmeticorum libri duo (1575)[16], ceci à la suite d'un article de G. Vacca de 1909, qui influença Moritz Cantor[17]. 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, qui est le passage du cas n au cas n+1 (mais celle-ci n'est pas énoncée comme un lemme, en vue de la proposition précédente). D'autre part il apparaît, d'après la correspondance de Pascal, que celui-ci a lu Maurolico. Cependant un article de Hans Freudenthal (1953)[18], montre 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[19].

Récurrence simple sur les entiers

Pour démontrer une propriété portant sur tous les entiers naturels, comme par exemple 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 de la récurrence ;
  • Pour tout entier n, (P(n)  \Rightarrow P(n+1)) : c'est l'hérédité.

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).

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, nE. La récurrence se réénonce alors de façon équivalente ainsi :

Soit E un sous-ensemble de N, si :
  • 0 ∈ E
  • nE ⇒ n+1 ∈ E (pour tout nN)
Alors E = N.

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 nk, [P(n) ⇒ P(n+1)] ;
Alors pour tout entier nk, 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(2n)), etc.

Exemple 1 : la somme des n premiers entiers impairs

Les entiers impairs sont les entiers de la forme 2n+1 (le premier, obtenu pour n=0, est 1). On déduit d'une identité remarquable bien connue que 2n+1 ajouté au carré de n donne le carré du nombre suivant :

n2+2n+1 = (n+1)2

On va donc montrer par récurrence que la somme des n premiers entiers impairs est égale au carré de n :

1+3+ … + (2n-1) = n2.

Bien que l'écriture précédente puisse laisser entendre que 2n -1 > 3, on ne le supposera pas. La 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 à 02
  • hérédité : pour un entier n arbitraire, on suppose que 1+3+ … + (2n-1) = n2. Puisque l'entier impair qui suit 2n-1 est 2n+1, on en déduit que :
1+3+ … + (2n-1) + (2n+1) = n2+2n+1= (n+1)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.

Précautions à prendre

  • L’initialisation ne doit pas être oubliée. Voici un exemple un peu ad hoc mais qui illustre bien ceci. On montre facilement que les propriétés « 32n+6 - 2n est un multiple de 7 » et « 32n+4 - 2n est un multiple de 7 » sont toutes deux héréditaires. Cependant la première est vraie pour tout entier naturel n, alors que la seconde ne l'est pas car elle n’est jamais initialisable : en effet, en n=0 on a 34 - 1 = 80, qui n'est pas divisible par 7. Pour la première proposition :
  • on vérifie que si n = 0, 36 - 20 est bien un multiple de 7 (728 est bien un multiple de 7) ;
  • on montre que si 32n+6 - 2n est un multiple de 7, alors 32n+8 - 2n+1 est un multiple de 7 :
3^{2n+8} - 2^{n+1}\begin{array}[t]{l}= 9\times 3^{2n+6} - 2 \times 2^{n}\\
                                              = (7+2)\times 3^{2n+6} - 2 \times 2^{n}\\
                                              = 7\times 3^{2n+6} +2\times 3^{2n+6} - 2 \times 2^{n}\\
                                              = 7\times 3^{2n+6} +2( 3^{2n+6} -2^{n})
                           \end{array}
.
32n+6 - 2n 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. On montre pourtant, en utilisant les congruences modulo 7, qu'elle n'est vraie pour aucun entier (congruences que l'on pourrait d'ailleurs utiliser également pour démontrer la première propriété).
  • L’hérédité doit être démontrée pour tout entier n plus grand ou égal au dernier n₀ pour lequel la propriété a été démontrée directement (initialisation).
Si on prend, par exemple, la suite u_n = \frac{n^2 - n + 1}{n^2}, on peut observer que cette suite est croissante à partir de n = 2 car  u_{n+1} - u_n = \frac{n^2 - n - 1}{n^2(n+1)^2} > 0.
Si on cherche à démontrer que u_n \geq 1 pour tout  n \geq 1,
l’initialisation est facile à prouver car u1 = 1.
l’hérédité aussi car, la suite étant croissante, si u_n \geq 1 alors u_{n+1} \geq 1.
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

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 nN)
alors P(n) pour tout nN.

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.

On peut bien entendu généraliser à 3, 4 etc. Mais tous ces principes apparaissent comme des cas particuliers du principe de récurrence suivant, parfois appelé récurrence forte.

Récurrence forte

Il est parfois nécessaire, dans des raisonnements par récurrence, d’utiliser une version plus forte pour l’hérédité :

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

Donc pour démontrer la propriété au rang suivant on peut la supposer vraie pour tous les rangs inférieurs.

À nouveau cette propriété est en apparence plus forte que la récurrence simple, mais lui est en fait équivalente, puisque cela revient à démontrer la propriété « ∀kn P(k) » par récurrence simple[20].

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 premier.

  • 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 compris entre 2 et n possèdent un diviseur premier et on cherche à prouver qu’il en est de même de n + 1.
ou bien n + 1 est premier alors il possède un diviseur premier qui est lui-même
ou bien n + 1 est composé et il existe deux entiers d et d' compris entre 2 et n tels que n + 1 = dd'. Alors d et d' possèdent des diviseurs premiers qui sont aussi diviseurs de n + 1.

Bonne fondation

On peut réénoncer ce principe de façon à évacuer toute référence aux entiers : 0 et le successeur qui à n associe n+1, au profit de la seule relation d'ordre. En effet les deux hypothèses de récurrence peuvent se rassembler en une seule :

Soit P(n) une propriété définie sur N, si :
  • [∀k<n P(k)] ⇒ P(n) (pour tout nN)
alors P(n) pour tout entier nN.

(dans le cas où n = 0, l'hypothèse est vide).

C'est cette forme du raisonnement par récurrence qui se généralise directement aux bons ordres et (aux ordres bien fondés). Dans le cas des entiers l'équivalence démontrée ci-dessus utilise, entre autres, que le seul entier qui n'est pas le successeur d'un autre entier est zéro. C'est cette propriété qui n'est pas nécessairement vraie dans les ensembles bien ordonnés.

Un principe de récurrence alternatif

Dans son livre sur la fonction gamma[21], le mathématicien Emil Artin propose un principe de récurrence qui s'adapte bien au cas où la propriété se démontre facilement pour les puissances de 2. Son énoncé est le suivant:

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

L'originalité de ce principe 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 entier strictement plus grand. Ce qui donne une preuve de la propriété sur tous les entiers en zigzag. Notons que cette idée peut se généraliser de 2 façons :

D'abord, en remplaçant l'hypothèse :

  • si pour tout nN, P(n)P(2n), par :
  • si pour tout nN, P(n)P(f(n)), où f est n'importe quelle fonction applicative strictement croissante sur les entiers.

Même mieux en la remplaçant par :

  • si pour tout nN [ P(n) ⇒ ∃pN, (n<p et P(p)) ], qui s'affranchit de la considération d'une fonction particulière.

D'autre part, avec cette généralisation, la règle d'initialisation :

  • si P(1) ( qui par rebours implique P(0) )

peut être remplacée (mais pas dans l'exemple de Artin qui nécessite que la propriété soit vérifiée par un entier non nul) par  :

  • s'il existe nN, P(n).

Ce qui nous donne le principe de récurrence suivant :

Soit P(n) une propriété définie sur N :
  • s'il existe nN, P(n),
  • si pour tout nN [ P(n) ⇒ ∃pN, (n<p et P(p)) ],
  • et si pour tout nN, P(n+1)P(n),
alors, pour tout entier nN, P(n).

Bon ordre et principe de descente infinie de Fermat

De façon alternative à la récurrence, en particulier à la récurrence forte, on peut utiliser le principe de descente infinie illustré par Pierre Fermat ; c'est une conséquence de la propriété de bon ordre, qui dit que tout sous-ensemble non vide de N a un plus petit élément, équivalente à la propriété de récurrence. On montre en fait que la propriété de récurrence donnée précédemment, qui ne dépend que de l'ordre, est une autre façon de formuler la propriété de bon ordre (sachant que la relation « ≤ » est totale).

Réénonçons tout d'abord cette récurrence de façon ensembliste. Cela revient à dire que pour tout sous-ensemble E de N :

si ([∀kN] k<nkE) ⇒ nE (pour tout nN)
alors E = N.

En reformulant par contraposée l'hypothèse de récurrence ci-dessus, on obtient que, pour tout nN :

nE ⇒ (∃kN) k <n & kE

c'est-à-dire que le complémentaire de E dans les entiers — notons-le EC — n'a pas de plus petit élément. Par ailleurs :

E = N si et seulement si EC = ∅.

Sachant que l'ordre sur N est total, il y a donc équivalence entre l'énoncé de récurrence sous sa dernière forme et l'énoncé :

tout sous-ensemble E de N qui n'a pas de plus petit élément est vide[22].

qui n'est autre que la contraposée de la propriété de bon ordre.

On a donc montré l'équivalence entre la propriété de récurrence simple sur N (via la propriété de récurrence forte) et la propriété de bon ordre sur N. 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, qui est d'ailleurs une conséquence de la propriété de récurrence. On utilise également des propriétés de compatibilité de l'ordre usuel sur les entiers et de la relation de successeur, y = x +1, essentiellement que l'ordre est obtenu en itérant celle-ci[23].

On peut remarquer que si l'on se contente de prouver la propriété de récurrence à partir de celle de bon ordre, et non l'équivalence, la preuve est particulièrement simple. Pour une propriété P héréditaire 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 n'existe que si cet ensemble est non vide. Si ce minimum est 0 cela contredit l'initialisation. Si ce minimum est le successeur d'un entier, ce dernier contredit l'hérédité. L'ensemble des entiers ne vérifiant pas P est donc vide : tout entier vérifie P.

De N est bien ordonné, on déduit directement qu'il n'existe pas de suite infinie strictement décroissante sur N[24], d'où le nom de « descente infinie » (dans le raisonnement par descente infinie, il s'agit justement d'en établir une, dans le cadre d'un raisonnement par l'absurde).

Il est également possible dans un raisonnement d'exploiter directement la propriété de bon ordre, appelée parfois dans ce cadre principe du minimum. Par exemple si on reprend l'un des premiers exemples connus de raisonnement par descente infinie, l'existence pour tout nombre d'un diviseur premier[8], on peut, en raisonnant par l'absurde, établir une suite infinie de diviseurs successifs stricts (descente infinie), ou choisir directement le plus petit diviseur d'un nombre donné (bon ordre) et montrer qu'il est premier.

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[25]. 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) et cela nécessiterait une infinité d’implications. Comme une démonstration est finie, une telle démonstration ne vaudra donc que pour un entier n fixé à l'avance. L'hypothèse de récurrence permet 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 de la théorie des ensembles, plus puissante. 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 directemement des théorèmes d'incomplétude de Gödel (1931) que non. En effet, pour toute axiomatisation raisonnable, par exemple la théorie des ensembles ZFC, chacun de ces deux théorèmes fournit une propriété des entiers démontrable pour n'importe quel entier fixé à l'avance, mais pourtant on ne peut démontrer cette propriété pour tout entier n, par récurrence ou tout autre moyen disponible par l'axiomatisation.

On a pu préférer déduire la propriété de récurrence pour les entiers de celle de bon ordre sur les entiers, et donc axiomatiser cette dernière, par exemple dans l'enseignement secondaire français des années 1970[réf. nécessaire]. Cela ne change rien sur le fond aux remarques qui précèdent.

En analyse non standard, on introduit un prédicat primitif, être standard, qui ne vérifie pas le principe de récurrence.

Énoncé formel du principe de récurrence

Formellement le principe de récurrence s'énonce comme un axiome ainsi :

 \forall P \subseteq \mathbb N \quad (P(0)   \wedge   ( \forall n\in \mathbb N, P(n) \Rightarrow P(n+1))) \Rightarrow (\forall n \in \mathbb N, P(n))

La quantification sur P est une quantification qui porte sur une fonction[26], on dit qu'il s'agit d'une quantification du second ordre. C'est cet aspect qui fait de l'axiome de récurrence un axiome très différent des autres axiomes qui régissent les entiers naturels.

Comme expliqué plus haut, en théorie des ensembles ce principe n'est plus un axiome mais un théorème (qui peut donc se déduire). Dans ce cas il s'écrit :

\forall P \subseteq \mathbb N \quad [0\in P   \land \forall n (n \in P \Rightarrow   n^+ \in P )] \Rightarrow \mathbb{N} \subseteq P

n+ est le successeur de n.[27] Pour l'utiliser il suffit de prendre P comme l'ensemble des entiers naturels qui vérifient le prédicat en question.

Généralisations

Le raisonnement par récurrence se généralise naturellement, sous la forme de la récurrence bien fondée indiquée ci-dessus, aux ensembles sur lesquels on peut définir un bon ordre, voir nombre ordinal et récurrence transfinie, ou simplement une relation bien fondée.

On peut le généraliser pour démontrer non plus des propriétés universelles sur les entiers naturels, mais par exemple sur les suites d'entiers ou sur les fonctions des entiers vers les entiers.

Notes

  1. Jean Itard, Les livres arithmétiques d'Euclide, Hermann 1961, cité par Roshdi Rashed (1972), et Fabio Acerbi (2000).
  2. voir parmi les références Roshdi Rashed (1972), et Fabio Acerbi (2000).
  3. Traité du triangle arithmétique.
  4. Pour une discussion précise de ce texte et de ce qu'il peut signifier pour Pascal, voir l'article de Fabio Acerbi en référence, introduction et note 13 p 4.
  5. D'après Wallis lui-même, voir Cajori (1918)
  6. en 1686, Acta eruditorum, d'après Cajori (1918).
  7. selon 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. Poincaré), au moins dans les milieux universitaires.
  8. a  et b Éléments d'Euclide livre IX proposition 31
  9. Grassmann, Lehrbuch der Arithmetik, 1861
  10. 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 Hubert C. Kennedy, The mathematical philosophy of Giuseppe Peano, philosophy of Science vol. 30, n° 3, Juillet 1963, disponible ici [1](au 31 juillet 2007).
  11. Richard Dedekind, Stetigkeit und Irrationale Zahlen, Braunschweig 1872.
  12. Éléments d'Euclide livre IX, prop 20. Euclide utilise pourtant un raisonnement par l'absurde, en supposant que l'ensemble des nombres premiers est fini ! Voir également la citation de Jean Itard, paragraphe précédent, et Fabio Acerbi (2000) p16.
  13. Rashed (1972), Katz (1998), pp. 255 et 258.
  14. Katz (1998) pp 256-259
  15. Rabinovitch (1970), Katz pp 302-306
  16. Francesco Maurolico, Arithmeticorum libri duo, Texte original sur Gallica.
  17. Voir l'article de Bussey (1917).
  18. D'après Rashed (72)
  19. Le nom de Maurolico n'apparait pas dans l'index du livre de Katz (95, 98), qui s'intéresse pourtant à plusieurs reprises à la récurrence. De façon symptomatique, 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 à Bussey (1917) !
  20. Evidemment cette équivalence demande d'avoir supposé quelques propriétés de compatibilité de l'ordre et du successeur.
  21. Emil Artin, "The Gamma function", in Rosen, Michael (ed.) Exposition by Emil Artin: a selection; History of Mathematics 30. Providence, RI: American Mathematical Society (2006).
  22. En l'absence de la totalité de la relation « ≤ », on a l'équivalence seulement avec la bonne fondation.
  23. c'est la clôture réflexive et transitive de la relation de succession y = x+1
  24. la réciproque est vraie, elle demande l'axiome du choix (dépendant), voir relation bien fondée.
  25. Par exemple Weis et Leroy, Le langage CAML, InterEditions 1993, p???, 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.
  26. ou sur un prédicat qui peut être vue comme une fonction d'un type particulier.
  27. Paul Halmos Naive set theory Van Nostrand, traduction française J. Gardelle Introduction à la théorie des ensembles Mouton Paris/La Haye 1970, chap. 12 p.58

Bibliographie

Plusieurs des articles historiques spécialisés (Acerbi, Rashed…) commencent par un panorama plus général.

  • Fabio Acerbi (2000), Plato: Parmenides 149a7-c3. A Proof by Complete Induction?, Archive for History of Exact Sciences 55 (2000), p. 57-76, accessible en ligne [2]
  • W. H. Bussey (1917). The Origin of Mathematical Induction. The American Mathematical Monthly 24 (5): 199-207, accès restreint en [3]
  • Florian Cajori (1918), Origin of the name mathematical induction, in The American math. Monthly, 25, 1918, no 5, p. 197-201, accès restreint en [4]
  • Richard Dedekind (1888), Was sind und was sollen die Zahlen? (« Que sont et que doivent être les nombres ? »), Braunschweig
  • Hans Freudenthal (1953), Zur Geschichte der vollständigen Induction, Archives Internationales d'Histoire des Sciences 6, p. 17-37.
  • Victor J. Katz (1995) et (1998), A History of Mathematics: An Introduction, 2nd ed. en 1998, Addison-Wesley. ISBN 0321016181.
  • Giuseppe Peano (1889), 1Arithmetices principia, nova methodo exposita (« Les principes de l'arithmétique, nouvelle méthode d'exposition »), Bocca, Turin, rep. Opera Scelte vol II ed. cremonese Roma 1958, original en latin traduit en anglais (partiellement) dans From Frege to Gödel : a source book in mathematical logic, Jean van Heijenoort Ed.
  • Nachum L. Rabinovitch (1970), Rabi Levi Ben Gershon and the Origins of Mathematical Induction, Archive for the History of Exact Science 6, p. 237-248, accès restreint chez l'éditeur.
  • Roshdi Rashed (1972), L'induction mathématique: al-Karajī, as-Samaw'al, Archive for History of Exact Sciences 9, p. 1-12, accès restreint chez l'éditeur.
  • G. Vacca (1909), Maurolycus, the first discoverer of the principle of mathematical induction, in Bull. of Am. math. Society, vol. XVI, 1909, p. 70-73, disponible en ligne [5], version française Sur le principe d'induction mathématique dans la Revue de Métaphysique et de morale, 19, 1911, p. 30-33, disponible sur le site de la BNF [6]
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. Rashed (1972), introduction, voir plutôt Bussey (1917) et Freudenthal (1953).
  • Mohamed Yadegari (1978), The Use of Mathematical Induction by Abu Kamil Shuja' Ibn Aslam (850-930), Isis, Vol. 69, No. 2 (Jun., 1978), p. 259-262, accès restreint en [7]
  • Portail des mathématiques Portail des mathématiques

Ce document provient de « Raisonnement par r%C3%A9currence ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Raisonnement Par Récurrence de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Raisonnement par recurrence — Raisonnement par récurrence En mathématiques, le raisonnement par récurrence 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… …   Wikipédia en Français

  • Raisonnement par récurrence — ● Raisonnement par récurrence démonstration par laquelle on étend à une série de termes homogènes la vérité d une propriété d au moins deux de ces termes …   Encyclopédie Universelle

  • Raisonnement par récurrence — En mathématiques, le raisonnement par récurrence 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 …   Wikipédia en Français

  • Démonstration par récurrence — Raisonnement par récurrence En mathématiques, le raisonnement par récurrence 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… …   Wikipédia en Français

  • Définition par récurrence — Pour les articles homonymes, voir Définition (Homonymie). En mathématiques une définition par récurrence d une fonction définie sur les entiers et à valeurs dans un ensemble donné utilise, pour définir la valeur de la fonction en un entier donné …   Wikipédia en Français

  • Récurrence en mathématiques — Raisonnement par récurrence En mathématiques, le raisonnement par récurrence 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… …   Wikipédia en Français

  • récurrence — [ rekyrɑ̃s ] n. f. • 1842 anat.; de récurrent 1 ♦ Math., littér. Retour, répétition. « une récurrence des émotions de terreur que sa présence m infligeait dans cette salle » (Bourget). Phénomène répétitif. 2 ♦ Log., sc. Raisonnement,… …   Encyclopédie Universelle

  • Recurrence transfinie — Récurrence transfinie La récurrence transfinie, appelée aussi sous l influence anglaise induction transfinie, permet de construire des objets et de démontrer des théorèmes sur des ensembles infinis. Elle généralise la récurrence ordinaire sur N… …   Wikipédia en Français

  • Récurrence finie — Récurrence transfinie La récurrence transfinie, appelée aussi sous l influence anglaise induction transfinie, permet de construire des objets et de démontrer des théorèmes sur des ensembles infinis. Elle généralise la récurrence ordinaire sur N… …   Wikipédia en Français

  • Récurrence semifinie — Récurrence transfinie La récurrence transfinie, appelée aussi sous l influence anglaise induction transfinie, permet de construire des objets et de démontrer des théorèmes sur des ensembles infinis. Elle généralise la récurrence ordinaire sur N… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”