Définition par récurrence

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques une définition par récurrence d'une fonction définie sur les entiers et à valeurs dans un ensemble donné, on parle souvent dans ce cas de suite plutôt que de fonction, 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. À la différence d'une définition usuelle, on utilise le nom de l'objet que l'on définit dans sa définition même.

De telles définitions se généralisent aux ordinaux et en général aux ensembles bien ordonnés, et 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. Dans le cas des entiers elle est suffisamment intuitive pour être employée sans autre justification.

[modifier] Définition par récurrence sur les entiers

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

Une définition légèrement 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 de nombre premier 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. Cette différence entre les deux manières de procéder illustre la différence entre le raisonnement par récurrence forte et celui par récurrence faible.