Suite définie par récurrence

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, une suite définie par récurrence est une suite définie par son (ou ses) premier(s) terme(s) et par une relation de récurrence, qui définit chaque terme à partir du précédent ou des précédents lorsqu'ils existent.

Une relation de récurrence est une équation dans laquelle l'expression de plusieurs termes de la suite apparait, par exemple :

u_{n+2}-{\sqrt {2u_{n+3}+u_{n}}}=0

ou

u_{n^{2}}=u_{n}

ou

(u_{n+2})^{2}-u_{n}-u_{n+1}=0

ou si l'on se place dans les suites de mots sur l'alphabet $\{a,b\}$ :

\alpha _{n+1}=a\alpha _{n}bb

Si la relation de récurrence a une « bonne » présentation, cela permet de calculer l'expression du terme d'indice le plus élevé en fonction de l'expression des autres. Par exemple dans la dernière équation, si l'on admet que les $u_{n}$ sont des réels positifs, on peut écrire :

u_{n+2}={\sqrt {u_{n+1}+u_{n}}}.

Une relation de récurrence et la donnée de « suffisamment » de termes initiaux permettent souvent de déterminer l'expression de tous les termes d'une suite (voir définition par récurrence).

Une relation de récurrence très simple est celle qui lie le terme d'indice n + 1 au terme d'indice n.

Exemple — On définit les puissances

z^{n}

d'une variable

z

par la relation de récurrence :

z^{n+1}=z\;\times z^{n}

et l'initialisation

z^{0}=1

.

Exemple — La suite de Fibonacci est définie par la donnée de

u_{0}=1

et

u_{1}=1

et par la relation de récurrence

u_{n+2}=u_{n}+u_{n+1}

; cette relation de récurrence est dite « linéaire ».

Définition

Une relation de récurrence est une équation qui exprime chaque élément de la suite comme une fonction des éléments précédents. Pour une suite où la relation de récurrence ne faisant appel qu'à l'élément précédent (une relation du premier ordre), on peut écrire la relation sous la forme :

\forall n>0,\ u_{n}=\varphi (n,u_{n-1}),

avec

\varphi :\mathbb {N} \times X\to X

une fonction, où $X$ est l'ensemble de définition des termes de la suite. Toute la suite est donc définie à partir du terme initial $u_{0}\in X$ . La définition de relations de récurrence appelant plusieurs termes se fait de façon similaire. Une récurrence d'ordre $k$ s'écrit donc

u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{ pour }}\quad n\geq k,

où $\varphi :\mathbb {N} \times X^{k}\to X$ est une fonction qui implique $k$ éléments consécutifs de la suite. La caractérisation de la suite nécessitera donc de donner $k$ valeurs initiales.