Utilisateur:Asram/Suites

Ceci est un brouillon

En mathématiques, on appelle suite récurrente linéaire d’ordre p toute suite à valeurs dans un corps commutatif $\mathbb {K}$ (généralement $\mathbb {C}$ ou $\mathbb {R}$ ) définie par une relation de récurrence du type :

\forall n,u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}

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

Les suites récurrentes linéaires d’ordre 1 s’appellent plus simplement suites géométriques de raison $a_{0}$ .

Les suites récurrentes linéaires d’ordre 2 interviennent dans plusieurs domaines, par exemple en analyse numérique, pour la résolution approchée d'équations aux dérivées partielles par la méthode des différences finies, en algèbre linéaire pour le calcul de certains déterminants. Le plus célèbre et sans doute le plus ancien exemple est la suite de Fibonacci.
La détermination de telles suites passe par la résolution d'une équation du second degré, dite équation caractéristique.

Plus généralement, pour l'étude des suites récurrentes linéaires d'ordre p, on introduit une équation caractéristique de degré p, et la série génératrice associée à la suite. Celle-ci est une fraction rationnelle qui, décomposée en éléments simples, se développe en série entière, ce qui permet de déterminer la forme générale des solutions et donne un moyen concret d'en calculer le terme général. On peut également considérer l'ensemble des suites récurrentes linéaires d'ordre p comme un espace vectoriel décomposable par le lemme des noyaux, ce qui ramène son étude à des sous-espaces plus simples.

Suite récurrente linéaire d’ordre 1

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

Si la relation de récurrence est $\forall n,u_{n+1}=q\,u_{n}$ , le terme général est

u_{n}=u_{0}q^{n}

Suite récurrente linéaire d’ordre 2

Lorsque p=2, a et b étant deux scalaires fixés de $\mathbb {K}$ avec b non nul, la relation de récurrence est du type :

\forall n,u_{n+2}=au_{n+1}+bu_{n}

(R).

Une suite géométrique de raison r non nulle vérifie cette relation si et seulement si le nombre r est solution de l'équation, dite caractéristique :

X^{2}-aX-b=0

.

Dans le cas où l'équation caractéristique admet deux racines distinctes $r_{1}$ et $r_{2}$ , le terme général d'une suite solution est

u_{n}=\lambda r_{1}^{n}+\mu r_{2}^{n}

,

où $\lambda$ et $\mu$ sont l'unique solution du système de Cramer :

{\begin{cases}\lambda +\mu =u_{0}\\\lambda r_{1}+\mu r_{2}=u_{1}\end{cases}}

.

Une démonstration par récurrence établit ce résultat.

Dans le cas où elle admet une racine double $r$ (nécessairement non nulle), on vérifie que la suite de terme général $v_{n}=v_{n}/r^{n}$ est arithmétique (sachant qu'alors $a=2r$ et $b=-r^{2}$ ) :

v_{n+2}-v_{n+1}=v_{n+1}-v_{n}

.

Elle s'écrit donc sous la forme

v_{n}=\lambda n+\mu

et l'on en déduit l'expression :

v_{n}=\lambda nr^{n}+\mu r^{n}

.

Lorsque a, b et les termes de la suite sont à valeurs réelles, on peut chercher à déterminer une expression de $u_{n}$ qui ne fassent intervenir que des nombres réels. Lorsque l'équation caractéristique a un discriminant $\Delta =a^{2}+4b$ positif ou nul, les expressions précédentes conviennent, car alors les scalaires $\lambda$ et $\mu$ sont réels. Sinon, les racines de $X^{2}-aX-b$ sont deux complexes conjugués $\rho e^{i\theta }$ et $\rho e^{-i\theta }$ . Le terme général de la suite est alors de la forme

u_{n}=\lambda \rho ^{n}e^{in\theta }+\mu \rho ^{n}e^{-in\theta }

.

Puisque $u_{n}$ est réel, il est égal à sa partie réelle, et

u_{n}=\rho ^{n}(Re(\lambda )cos(n\theta )-Im(\mu )sin(n\theta )+Re(\mu )cos(n\theta )-Im(\lambda )sin(n\theta ))

et l'on obtient l'expression :

u_{n}=\rho ^{n}(A\cos(n\theta )+B\sin(n\theta ))\,

avec

A,B

réels.

Suite récurrente d’ordre p

Sous-espace vectoriel de dimension p

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

\forall n,u_{n+p}=a_{0}u_{n}+a_{1}u_{n+1}+\cdots +a_{p-1}u_{n+p-1}

, avec

a_{0}

non nul,

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

De plus, ce sous espace vectoriel est de dimension p. En effet, il existe un isomorphisme d’espace vectoriel entre $E_{R_{p}}$ et l’ensemble $\mathbb {K} ^{p}\,$ : à chaque suite de terme général $u_{n}$ de $E_{R_{p}}$ , on associe le p_uplet $(u_{0},u_{1},\cdots ,u_{p-1})$ .

Interprétation matricielle

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

U_{n}=(u_{n},u_{n+1},\cdots ,u_{n+p-1})

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

U_{n+1}=AU_{n}

où

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

L'équation caractéristique est liée au polynôme caractéristique de la matrice A : il s'agit de $P(X)=X^{p}-\sum _{i=0}^{p-1}a_{i}X^{i}$ . La matrice A est la matrice compagnon de ce polynôme.

Résolution théorique

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

On peut montrer que toute suite de terme général $Q(n)r_{i}^{n}$ est élément du noyau de $(f-r_{i}Id)^{\alpha _{i}}$ pour peu que le degré de Q soit inférieur strictement à $\alpha _{i}$ . Cette démonstration se fait par récurrence sur $\alpha _{i}$ . Comme les suites $(n^{j}r_{i}^{n})_{n\in \mathbb {N} }$ , pour j = 0 à $\alpha _{i}-1$ forment une partie libre de $\alpha _{i}$ éléments, mais le cas d'une racine nulle se traite aisément par décalage d'indice</ref>, la famille de toutes les suites $(n^{j}r_{i}^{n})_{n\in \mathbb {N} }$ , pour j = 0 à $\alpha _{i}-1$ et pour i = 1 à k forme une famille libre de $\alpha _{1}+\alpha _{2}+\cdots +\alpha _{k}=p$ éléments de $E_{R_{p}}$ (de dimension p) donc une base de $E_{R_{p}}$ . Les éléments de $E_{R_{p}}$ sont donc des sommes coefficientées de suites dont le terme général est $Q(n)r_{i}^{n}$ avec Q de degré strictement inférieur à $\alpha _{i}$ .

Résolution pratique

Dans le cas où la matrice A est diagonalisable, ce qui équivaut exceptionnellement au cas où le polynôme P admet p racines distinctes, une base de $E_{R_{p}}$ est immédiate : il s'agit des suites géométriques $r_{i}^{n}$ pour i variant de 1 à p.

Dans le cas général, on introduit le polynôme réciproque D de P, défini par :

D(X)=1-\sum _{i=0}^{p-1}a_{i}X^{p-i}

et la série génératrice G associée à la suite de terme général $u_{n}$ définie par :

G(X)=\sum _{n=0}^{\infty }u_{n}X^{n}

,

on peut montrer que la suite vérifie la relation $E_{R_{p}}$ si et seulement si le produit de Cauchy $N=GD$ est un polynôme de degré strictement inférieur à p. Dans ce cas, $G={\frac {\mathrm {N} }{\mathrm {D} }}$ est une fraction rationnelle développable en série entière au voisinage de 0, grâce à une décomposition en éléments simples, et par identification, ce développement donne l'expression des $u_{n}$ .