récurrence

Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».

Épistémologie, Mathématiques

Principe fondamental suivant : soit une propriété P, énoncée pour un nombre entier n. On notera P_n la proposition « P est vraie pour n ». Si P_l est vraie et si, pour tout m, entier, P_m-l, entraîne P_m, alors, pour tout n, P_n.

Poincaré énonce ainsi la démonstration par récurrence : « On établit d'abord un théorème pour n = 1 ; on montre ensuite que s'il est vrai de n – 1, il est vrai de n, et on en conclut qu'il est vrai pour tous les nombres entiers. » Ce principe est souvent appelé principe d'induction complète, par opposition à l'induction employée en physique.

Sa première apparition dans la littérature mathématique est due à Pascal dans la « conséquence 12^e des définitions » du Traité du triangle arithmétique, où il écrit : « Quoique cette proposition ait une infinité de cas, j'en donnerais dem. Bien courte, en supposant deux lemmes. Le 1, qui est évident de soi-même, que cette proposition se rencontre dans la seconde base. Le 2, que si cette proposition se trouve dans une base quelconque, elle se retrouve 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... Il faut donc seulement démontrer le second lemme »⁽¹⁾.

Poincaré juge qu'il s'agit « là du raisonnement mathématique par excellence »⁽²⁾.

Vincent Jullien