Grand oral: qu’est-ce que le raisonnement par récurrence ?

« Introduction : Comme la dit Henri point carré « La récurrence est le raisonnement mathématique par excellence » et elle est irréductible à la logique classique car » elle est « l’affirmation de la puissance de l’esprit qui se sait capable de concevoir la répétition indéfinie d’un même acte dès que cet acte est une fois possible » Mais qu’est-ce que le raisonnement par récurrence dans sa forme actuelle : 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, dans sa forme actuelle, consiste à démontrer les points suivants : -la propriété est valable initialement pour un entier n 0 -chaque fois que cette propriété est vraie pour un certain entier naturel n ≥ n0, elle est également satisfaite par son successeur Cependant, il y a eu de nombreuse étapes avant d’aboutir au puissant raisonnement par récurrence que nous connaissons aujourd’hui Quelle sont les grandes étapes historiques de l’élaboration du raisonnement par récurrence ? Historiquement, le raisonnement par récurrence a eu du mal à être formalisé comme on le connaît : il a longtemps été utilisé intuitivement sans le nommer Et d’ailleurs on fait souvent remonter la récurrence à Euclide ce qui est à la fois vrai et faux.

L’exemple habituellement donné est la proposition 20 du livre IX des Éléments (composés vers l’an 300 avant notre ère), où Euclide affirme qu’à toute liste de nombres premiers on peut en adjoindre un de plus Il y a donc l’esquisse d’une récurrence, mais elle n’est pas explicite.

En outre, l’idée d’une infinité de nombres premiers est absente malgré la présence d’un calcul itératif Il existe de nombreux exemples, européens ou arabe d’utilisation implicite de la récurrence, comme celui Al-Karaji qui l’utilisa pour établir la formule du binôme de Newton. Cependant Il semble bien que Pascal soit le premier à avoir énoncé nettement ce principes et à en avoir reconnu la puissance durant le 16 ème siècle En effet, nous trouvons dans le Traité du triangle arithmétique de Blaise Pascal, écrit en 1654 ce qui est généralement considéré comme la première utilisation tout à fait explicite du raisonnement par récurrence: « Quoique cette proposition ait une infinité de cas, j'en donnerai une démonstration bien courte, en supposant deux lemmes : Le 1, qui est évident de soi-même, que cette proportion se rencontre dans la seconde base 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.

» On voit clairement ici le progrès réalisé.

Au langage près, on est bien en présence d’une récurrence telle que nous la pratiquons : l’initialisation par le lemme 1 puis par l’expression d’une hérédité. Cependant cette justification ne peut constituer une démonstration de la validité du principe de récurrence.

En effet, pour démontrer une propriété 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. De plus, Nous remarquons que Pascal ne fait pas appelé à l’axiome de récurrence et pour cause, il ne sera introduit que deux siècle plus tard par les travaux de Dedekind et de Peano C’est seulement au cours du 19éme siècle que le raisonnement par récurrence est de plus en plus utilisé.

Nous aboutissons finalement à sa formalisation et à son axiomatisation, d'abord partiellement par Richard Dedekind en 1888 puis indépendamment par Giuseppe Peano en 1889 Pour Dedekind il s'agit d'achever l'arithmétisation des réels par récurrence, en donnant un cadre formel. Peano quant à lui, en s’appuyant sur des travaux antérieurs de Dedekind construisit l'ensemble N des nombres entiers naturels au moyen de 5 axiomes, par une méthode proche du raisonnement par récurrence Dans les deux cas la récurrence n'est plus simplement un principe de démonstration.... »