Suite récurrente linéaire

En mathématiques, on appelle suite récurrente linéaire d’ordre p toute suite à valeurs dans un corps commutatif K (par exemple ℝ ou ℂ ; on ne se placera que dans ce cas dans cet article) définie pour tout ${\displaystyle n\geq n_{0}}$ par une relation de récurrence linéaire de la forme

${\displaystyle \forall n\geq n_{0}\quad u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}}$

où ${\displaystyle a_{0}}$, ${\displaystyle a_{1}}$, …${\displaystyle a_{p-1}}$ sont p scalaires fixés de K (${\displaystyle a_{0}}$ non nul).

Une telle suite est entièrement déterminée par la donnée de ses p premiers termes et par la relation de récurrence.

Les suites récurrentes linéaires d’ordre 1 sont les suites géométriques.

L'étude des suites récurrentes linéaires d'ordre supérieur se ramène à un problème d'algèbre linéaire. L'expression du terme général d'une telle suite est possible pour peu qu'on soit capable de factoriser un polynôme qui lui est associé, appelé polynôme caractéristique ; le polynôme caractéristique associé à une suite vérifiant la relation de récurrence ci-dessus est :

${\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}=X^{p}-a_{p-1}X^{p-1}-a_{p-2}X^{p-2}-\dots -a_{1}X-a_{0}.}$

Son degré est ainsi égal à l'ordre de la relation de récurrence. En particulier, dans le cas des suites d'ordre 2, le polynôme est de degré 2 et peut donc être factorisé à l'aide d'un calcul de discriminant. Ainsi, le terme général des suites récurrentes linéaires d'ordre 2 peut être exprimé en utilisant seulement les deux premiers termes, quelques valeurs constantes, quelques opérations élémentaires de l'arithmétique (addition, soustraction, multiplication, exponentielle) et les fonctions sinus et cosinus (si le corps des scalaires est le corps des réels). Une des suites de ce type est la célèbre suite de Fibonacci, qui peut s'exprimer à partir de puissances faisant intervenir le nombre d'or.

Les suites récurrentes linéaires d'ordre 1 sont les suites géométriques.

Si la relation de récurrence est ${\displaystyle u_{n+1}=qu_{n}}$, le terme général est ${\displaystyle u_{n}=u_{n_{0}}q^{n-n_{0}}}$.

a et b étant deux scalaires fixés de K avec b non nul, la relation de récurrence est

${\displaystyle u_{n+2}=au_{n+1}+bu_{n}\quad (R).}$

Les scalaires r tels que la suite ${\displaystyle (r^{n})_{n\in \mathbb {N} }}$ vérifie (R) sont les solutions de l’équation du second degré ${\displaystyle r^{2}-ar-b=0}$. Le polynôme ${\displaystyle X^{2}-aX-b}$ est alors appelé le polynôme caractéristique de la suite. Son discriminant est ${\displaystyle \Delta =a^{2}+4b}$. Il faudra alors distinguer plusieurs cas, selon le nombre de racines du polynôme caractéristique.

Le cas 1 se produit par exemple si ${\displaystyle K=\mathbb {R} }$ et si le discriminant ${\displaystyle \Delta =a^{2}+4b}$ est strictement positif, ou si ${\displaystyle K=\mathbb {C} }$ et ${\displaystyle \Delta \neq 0}$. De plus, si les deux racines ${\displaystyle r_{1},r_{2}}$ du polynôme ${\displaystyle X^{2}-aX-b}$ sont deux complexes conjugués ${\displaystyle \rho \mathrm {e} ^{\mathrm {i} \theta }}$ et ${\displaystyle \rho \mathrm {e} ^{-\mathrm {i} \theta }}$, alors le terme général d'une telle suite s'écrit également^[1] :

• ${\displaystyle \rho ^{n}(A\cos(n\theta )+B\sin(n\theta ))}$ avec A et B paramètres dans K (${\displaystyle =\mathbb {R} }$ ou ${\displaystyle \mathbb {C} }$, selon qu'on s'intéresse aux suites réelles ou complexes) déterminés par les deux premières valeurs de la suite.

Le cas 2 se produit lorsque ${\displaystyle \Delta =0}$ et alors, la racine double est ${\displaystyle r_{0}={\frac {a}{2}}}$.

On ne perd rien à la généralité de la suite en supposant que celle-ci est définie sur tout ℕ et pas seulement à partir de ${\displaystyle n_{0}}$. En effet, l'étude d'une suite u qui n’est définie qu’à partir de ${\displaystyle n_{0}}$ se ramène à celle de la suite v définie sur ℕ par ${\displaystyle v_{n}=u_{n+n_{0}}}$.

Si une suite u vérifie

${\displaystyle \forall n\in \mathbb {N} \quad u_{n+2}=au_{n+1}+bu_{n}\quad (R)}$

alors, elle peut être étendue aux indices négatifs et reliée aux puissances de la matrice (appelée matrice compagnon du polynôme caractéristique)

${\displaystyle P:={\begin{pmatrix}a&b\\1&0\end{pmatrix}}}$

(inversible puisque b ≠ 0) par :

${\displaystyle \forall n\in \mathbb {Z} \quad {\begin{pmatrix}u_{n+1}\\u_{n}\end{pmatrix}}=P^{n}{\begin{pmatrix}u_{1}\\u_{0}\end{pmatrix}}}$.

Ceci permet de montrer que pour v égale à u ou à toute autre suite vérifiant la même relation de récurrence (R) et pour tous entiers i, j, k, l et r^[2],[3] :

${\displaystyle i+j=k+l\Rightarrow u_{i+r}v_{j+r}-u_{k+r}v_{l+r}=(-b)^{r}(u_{i}v_{j}-u_{k}v_{l})}$.

En particulier :

${\displaystyle {\text{si }}u_{0}=0{\text{ alors}}\quad \forall m,n,r\in \mathbb {Z} \quad u_{n}v_{m+r}-u_{r}v_{m+n}=(-b)^{r}u_{n-r}v_{m}}$.

Si l'on appelle ${\displaystyle (R_{p})}$ la relation de récurrence :

pour tout entier n, ${\displaystyle u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}}$

et si l'on note ${\displaystyle E_{R_{p}}}$, l’ensemble des suites à valeurs dans K et vérifiant ${\displaystyle (R_{p})}$, on démontre que ${\displaystyle E_{R_{p}}}$ est un sous-espace vectoriel de l'espace des suites à valeurs dans K. Cela tient à la linéarité de la relation de récurrence.

De plus, ce sous-espace est de dimension p. En effet, il existe un isomorphisme d'espaces vectoriels entre ${\displaystyle E_{R_{p}}}$ et ${\displaystyle K^{p}}$ : à chaque suite u de ${\displaystyle E_{R_{p}}}$, on associe le p-uplet ${\displaystyle (u_{0},u_{1},\cdots ,u_{p-1})}$. Il suffit alors de connaître une famille libre de p suites vérifiant ${\displaystyle (R_{p})}$, l’ensemble ${\displaystyle E_{R_{p}}}$ est alors engendré par cette famille libre.

La recherche du terme général et des suites particulières s’effectue en travaillant sur ${\displaystyle K^{p}}$. À chaque suite ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ on associe la suite ${\displaystyle (U_{n})_{n\in \mathbb {N} }}$ définie par

${\displaystyle U_{n}={\begin{pmatrix}u_{n}\\u_{n+1}\\\vdots \\u_{n+p-1}\end{pmatrix}}.}$

La relation de récurrence sur ${\displaystyle (u_{n})_{n\in \mathbb {N} }}$ induit une relation de récurrence sur ${\displaystyle (U_{n})_{n\in \mathbb {N} }}$

${\displaystyle U_{n+1}=AU_{n}}$ où

${\displaystyle A={\begin{pmatrix}0&1&0&\cdots &0\\0&0&1&\cdots &0\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &\cdots &0&1\\a_{0}&a_{1}&\cdots &\cdots &a_{p-1}\end{pmatrix}}}$

(A est la matrice compagnon du polynôme caractéristique de la suite).

Le terme général de la suite U est alors déterminé par^[4]

${\displaystyle U_{n}=A^{n}U_{0}.}$

Le problème semble alors terminé. Mais la réelle difficulté consiste alors à calculer ${\displaystyle A^{n}}$… On préfère déterminer une base de ${\displaystyle E_{R_{p}}}$.

Le polynôme caractéristique de la matrice A est ${\displaystyle P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}}$. Ce n'est pas un hasard si on le retrouve pour caractériser les suites ${\displaystyle u=(u_{n})_{n\in \mathbb {N} }}$ vérifiant ${\displaystyle R_{p}}$.

On note f la transformation linéaire qui, à une suite ${\displaystyle u=(u_{n})_{n\in \mathbb {N} }}$ associe la suite ${\displaystyle v=(v_{n})_{n\in \mathbb {N} }}$ définie par ${\displaystyle v_{n}=u_{n+1}}$. La condition « u vérifie ${\displaystyle R_{p}}$ » se traduit alors par P(f)(u) = 0. L'ensemble ${\displaystyle E_{R_{p}}}$ est donc le noyau de P(f). Si le polynôme P est scindé sur K (ce qui est toujours vrai si K = ℂ), il s'écrit ${\displaystyle P=\prod _{i=1}^{k}(X-r_{i})^{\alpha _{i}}}$, où ${\displaystyle r_{1},r_{2},\dots ,r_{k}}$ sont les racines de P et ${\displaystyle \alpha _{1},\alpha _{2},\dots ,\alpha _{k}}$ leurs ordres de multiplicité respectifs. Le noyau de P(f) est alors la somme directe des noyaux des ${\displaystyle (f-r_{i}\mathrm {Id} )^{\alpha _{i}}}$. Il suffit donc de trouver une base de chacun de ces noyaux pour déterminer une base de ${\displaystyle E_{R_{p}}}$ .

On peut montrer que toute suite de terme général ${\displaystyle Q(n)r_{i}^{n}}$ est élément du noyau de ${\displaystyle (f-r_{i}\mathrm {Id} )^{\alpha _{i}}}$ pour peu que le degré de Q soit strictement inférieur à ${\displaystyle \alpha _{i}}$. Cette démonstration se fait par récurrence sur ${\displaystyle \alpha _{i}}$. Comme les suites ${\displaystyle (n^{j}r_{i}^{n})_{n\in \mathbb {N} }}$, pour j = 0 à ${\displaystyle \alpha _{i}-1}$, forment une partie libre de ${\displaystyle \alpha _{i}}$ éléments^[5], les suites ${\displaystyle (n^{j}r_{i}^{n})_{n\in \mathbb {N} }}$, pour j de 0 à ${\displaystyle \alpha _{i}-1}$ et i de 1 à k, forment une famille libre de ${\displaystyle \alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=p}$ éléments de ${\displaystyle E_{R_{p}}}$ (de dimension p) donc une base de ${\displaystyle E_{R_{p}}}$. Les éléments de ${\displaystyle E_{R_{p}}}$ sont donc des sommes de suites dont le terme général est ${\displaystyle Q(n)r_{i}^{n}}$ avec degré de Q strictement inférieur à ${\displaystyle \alpha _{i}}$.

Si le polynôme caractéristique se scinde en ${\displaystyle (X-r_{1})(X-r_{2})}$ alors les polynômes Q sont de degré 0 et les éléments de ${\displaystyle E_{R_{2}}}$ sont des suites dont le terme général est ${\displaystyle \lambda _{1}r_{1}^{n}+\lambda _{2}r_{2}^{n}}$.

Si le polynôme caractéristique se scinde en ${\displaystyle (X-r_{0})^{2}}$ alors les polynômes Q sont de degré 1 et les éléments de ${\displaystyle E_{R_{2}}}$ sont des suites dont le terme général est ${\displaystyle (\lambda _{1}n+\lambda _{2})r_{0}^{n}}$.

• Série génératrice d'une suite récurrente linéaire
• Suite de Lucas
• Transformation binomiale

• Portail de l'analyse