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é, les valeurs de cette même fonction pour des entiers strictement inférieurs. De telles fonctions sont souvent appelées suites. À la différence d'une définition usuelle, on utilise le nom de l'objet que l'on définit (la fonction en l'occurrence) dans sa définition même.

De telles définitions se généralisent aux ordinaux et ensembles bien ordonnés, et plus généralement aux relations bien fondées. On parle également, et assez souvent dans le cas des bons ordres et des définitions bien fondées, de définition par induction (sur les entiers, sur tel bon ordre, sur les ordinaux etc.).

La correction d'une définition par récurrence, c'est-à-dire l'existence et l'unicité de la fonction ainsi définie, se démontre en théorie des ensembles, même si, en particulier dans le cas des entiers, elle est suffisamment intuitive pour être employée sans autre justification.

Définition par récurrence sur les entiers

Énoncé

L'ensemble des entiers naturels (on dira simplement entiers) est noté N. Étant donné une constante a et une fonction h définie de N × E dans E, la fonction f de N dans E définie par récurrence à partir de a et h est l'unique fonction qui vérifie pour tout entier n :

f(0) = a ;   f(n + 1) = h(n, f(n)).

Dans le cas où la fonction h ne dépend pas de son premier argument, on parle parfois de définition par itération. Par exemple l'addition d'un entier n à un entier a donné, se définit par itération à partir de la fonction successeur. La fonction factorielle se définit par récurrence à partie de la multiplication, récurrence qui n'est pas une itération.

Il ne s'agit pas d'une définition au sens ordinaire (une simple abréviation) : la fonction f est définie en fonction d'elle-même. Un théorème (ou un axiome) d'existence et d'unicité d'une fonction ainsi définie est nécessaire. L'unicité se démontre par récurrence. L'existence demande une construction ensembliste du graphe de la fonction.

Définition par récurrence sur la suite des valeurs

Une définition en apparence plus générale peut être donnée pour les entiers, en effet f(n + 1) peut dépendre de f(n) mais aussi de f(n-1). Ainsi on peut définir f(n+1) par récurrence grâce à f(0), f(1),..., f(n) et n, c'est la cas par exemple de la suite de Fibonacci qui utilise f(n + 1) et f(n) pour définir f(n + 2) (il faut alors bien veiller à définir f(0) et f(1)). Avec cette idée on peut aussi définir la suite des nombres premiers comme une suite définie par récurrence : p(1)=2 puis p(n) correspond au plus petit entier qui n'est divisible par aucun p(i) pour i inférieur à n (on parle de récurrence sur la suite des valeurs). Cette différence entre définition par récurrence sur la suite des valeurs et récurrence ordinaire reflète la différence entre le raisonnement par récurrence forte et celui par récurrence faible. On déduit l'un de l'autre en définissant par récurrence ordinaire la suite finie des n premières valeurs de la fonction : F(n) = (f(0), f(1),..., f(n)). Dans le cas de la suite de Fibonacci il suffit de définir par récurrence le couple F(n) = (f(n), f(n+1)).

Bibliographie

• Paul Halmos, Introduction à la théorie des ensembles [détail des éditions] (théorèmes d'existence et d'unicté pour la récurrence sur les entiers, et les récurrences ordinales).