Raisonnement par récurrence

Infos
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, ou plus généralement sur tous les entiers supérieurs à un entier donné. Le raisonnement par récurrence simple consiste à démontrer séparément les points suivants :
- Une propriété est vérifiée par un entier k, par exemple 0 ou 1 ;
- Si la propriété est vérifi
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, ou plus généralement sur tous les entiers supérieurs à un entier donné. Le raisonnement par récurrence simple consiste à démontrer séparément les points suivants :
- Une propriété est vérifiée par un entier k, par exemple 0 ou 1 ;
- Si la propriété est vérifiée par un entier, alors elle doit être vérifiée par son successeur, c'est-à-dire, l'entier qui le suit. Une fois cela établi, on en déduit que la propriété est vraie pour tous les entiers supérieurs à k. 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 ou informatique, pour des structures de nature arborescente, 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.

Historique

L'histoire du raisonnement par récurrence n'est pas chose simple. 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 Jean Itard, Les livres arithmétiques d'Euclide, Hermann 1961.. Ce point de vue est cependant assez peu partagé des autres historiensvoir par exemple, parmi les références Roshdi Rashed (1972), et Fabio Acerbi (2000)..

Le et ensuite

Sans que le consensus soit peut-être encore tout à fait établi, ceux-ci s'accordent généralement pour trouver dans le Traité du triangle arithmétique de Blaise Pascal, écrit en 1654 mais publié en 1665, la première utilisation 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 f est à s 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'infiniPour 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.. Toujours au , il faut mentionner Pierre FermatD'après Wallis lui-même, voir Cajori (1918) et Jacob Bernoullien 1686, Acta eruditorum, d'après Cajori (1918). qui critiquent tous deux la méthode d'inductionselon 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. 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Éléments d'Euclide livre IX proposition 31. 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 , 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 Grassmann, 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, n° 3, Juillet 1963, disponible ici (au 31 juillet 2007).. 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 1872Richard Dedekind, Stetigkeit und Irrationale Zahlen, Braunschweig 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. Florian Cajori (1918) la décèle dans la méthode cyclique de Bhaskara et dans la preuve d'Euclide de l'existence d'une infinité de nombres premiersÉ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.. 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 naturelsRashed (1972), Katz (1998), pp. 255 et 258., 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 naturelsKatz (1998) pp 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…)Rabinovitch (1970), Katz pp 302-306. 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)Francesco Maurolico, Arithmeticorum libri duo, sur Gallica., ceci à la suite d'un article de G. Vacca de 1909, qui influença Moritz CantorVoir l'article de Bussey (1917).. 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), 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 plusLe 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) !.

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, dans ce cas la propriété n'est démontrée vraie qu'à partir du rang k. La récurrence qui commence à 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, 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

Le premier entier impair est 1, le second 3, on admet que le n+1-ième entier impair s'écrit 2
n+1. On déduit d'une identité remarquable bien connue que ce nombre ajouté au carré de n donne le carré du nombre suivant : :n^2+2n+1 = (n+1)^2 On va donc montrer par récurrence que la somme des n premiers entiers impairs égale le 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

La formule du binôme de Newton affirme que pour tous réels a et b, et pour tout entier naturel n, on a : (a+b)^n=\sum_^n n \choose k a^kb^. L'élévation à la puissance n ou la sommation sur n indices se définissent elles-mêmes par récurrence (voir ci-après). Le raisonnement par récurrence est donc particulièrement adapté ici :
- Initialisation : L'identité est vraie pour n=1 ; elle s'écrit : (a+b)=1 \choose 0a+1 \choose 1b.
- Induction : Supposons l'identité annoncée vérifiée pour un entier naturel n donné. Calculons (a+b)^ : :: \begin (a+b)^ &= (a+b)^n.(a+b) \\ &= \left.(a+b) \\ &= \left+n \choose na^+n \choose 0b^ \\ &= \sum_^n+1 \choose ka^kb^ \end Par récurrence, on en déduit le résultat annoncé.

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 « 3^ - 2^ est un multiple de 7, n ≥ 3 » et « 3^ - 2^ est un multiple de 7, n ≥ 2 » sont toutes deux héréditaires. Cependant la première est vraie à partir de 3, alors que la seconde est toujours fausse car elle n’est jamais initialisable. En effet pour la première : :
- on vérifie que si n = 3, 3^ - 2^ est bien un multiple de 7 (728 est bien un multiple de 7) ; :
- on montrer que (pour tout n \geq 3) si 3^ - 2^ est un multiple de 7, alors 3^ - 2^ est un multiple de 7. :::3^ - 2^ = 9\times 3^ - 2 \times 2^. :::3^ - 2^ = (7+2)\times 3^ - 2 \times 2^. :::3^ - 2^ = 7\times 3^ +2\times 3^ - 2 \times 2^. :::3^ - 2^ = 7\times 3^ +2( 3^ -2^). ::3^ - 2^ 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 est fausse pour chaque entier n (argument 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_0 pour lequel la propriété a été démontrée directement (initialisation). :Si on prend, par exemple, la suite u_n = \frac, on peut observer que cette suite est croissante à partir de n = 2 car u_ - u_n = \frac > 0. :Si on cherche à démontrer que u_n \geq 1 pour tout n \geq 1, ::l’initialisation est facile à prouver car u_1 = 1. ::l’hérédité aussi car, la suite étant croissante, si u_n \geq 1 alors u_ \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+2) (pour tout nN) :alors P(n) pour tout nN. Cette propriété est en apparence plus forte que la récurrence simple, puis que l'on a une hypothèse supplémentaire à notre disposition, mais lui est en fait équivalente, puisque cela revient à démontrer 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) :
- ⇒ P(n+1) (pour tout nN) :alors P(n) pour tout entier nN. Bref, 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 simpleEvidemment cette équivalence demande d'avoir supposé quelques propriétés de compatibilité de l'ordre et du successeur.. 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
Sujets connexes
Al-Karaji   Analyse non standard   Arbre (mathématiques)   Axiome   Axiome du choix   Axiomes de Peano   Bhaskara   Blaise Pascal   Complémentaire (théorie des ensembles)   Congruence   Démonstration   Ensemble   Entier naturel   Euclide   Formulaire de mathématiques   Formule du binôme de Newton   Francesco Maurolico   Gersonide   Giuseppe Peano   Hermann Günther Grassmann   Informatique   John Wallis   Logique   Mathématiques   Moritz Cantor   Nombre ordinal   Nombre premier   Raisonnement par l'absurde   Relation bien fondée   Relation binaire   Relation de récurrence   Richard Dedekind   Récurrence transfinie   Suite de Fibonacci   Théorie axiomatique   Théorie des ensembles   Traité du triangle arithmétique   ZFC  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^