Suite récurrente linéaire d'ordre 1

Suite récurrente linéaire

En mathématiques, on appelle suite récurrente linéaire d’ordre p, toute suite à valeurs dans un corps K (généralement $\mathbb C$ ou $\R$) définie pour tout $n \geq n_0$ par la relation de récurrence suivante :

a₀, a₁, …a_{p − 1} étant p scalaires fixés de K (a₀ non nul), pour tout $n \geq n_0$, on a

$u_{n+p} = a_0u_n + a_1u_{n+1} + \cdots + a_{p-1}u_{n+p-1}$

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

Les suites récurrentes linéaires d’ordre 1 s’appellent plus simplement des suites géométriques de raison a₀. Concernant les suites récurrentes linéaires d'ordre 2, notons qu'on peut exprimer leur terme général sans avoir recours à la récurrence, plus précisément 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. Une des suites de ce type est la très célèbre suite de Fibonacci qui peut s'exprimer à partir de puissances faisant intervenir le nombre d'or. L’étude des suites récurrentes linéaires d’ordre p fait appel à la notion d’espace vectoriel et au calcul matriciel.

Suite récurrente linéaire d’ordre 1

• Voir article détaillé : Suite géométrique

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

Suite récurrente linéaire d’ordre 2

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

u_{n + 2} = au_{n + 1} + bu_n (R)

On va prouver que le terme général d'une telle suite est

• $\lambda r_1^n+ \mu r_2^n$ si r₁ et r₂ sont deux racines distinctes du polynôme X² − aX − b
• $(\lambda + \mu n) r_0^n$ si r₀ est racine double du polynôme X² − aX − b
• $(\lambda\cos(n\theta) + \mu\sin(n\theta))\rho^n\,$ pour une suite réelle quand ρe^iθ et ρe ^{− iθ} sont les deux racines complexes du polynôme X² − aX − b

On ne perd rien à la généralité de la suite en supposant que celle-ci est définie sur tout $\mathbb N$ et pas seulement à partir de n₀. En effet, si une suite (u) n’est définie qu’à partir de n₀, elle induit la création d’une suite (v) définie sur $\mathbb N$ en posant $v_n = u_{n + n_0}$.

L’idée est alors de rechercher des suites géométriques vérifiant la récurrence (R). C’est-à-dire chercher des scalaires r tels que la suite $(r^n)_{n \in \mathbb N}$ vérifie (R). On démontre aisément que ce problème équivaut à résoudre l’équation du second degré $r^2- ar - b = 0\,$. Le polynôme $r^2- ar - b \,$ est alors appelé le polynôme caractéristique de la suite. Son discriminant est $\Delta = a^2 + 4b\,$. Il faudra alors distinguer plusieurs cas, selon que le nombre de racines du polynôme caractéristique.

Si le polynôme possède deux racines distinctes

Soient r₁ et r₂ les deux racines distinctes. Les suites $(r_1^n)_{n \in \mathbb N}$ et $(r_2^n)_{n \in \mathbb N}$ vérifient (R) ainsi que toute suite dont le terme général serait $\lambda r_1^n + \mu r_2^n$ (cela tient au caractère linéaire de la récurrence). A-t-on alors trouvé toutes les suites vérifiant (R) ? Une suite vérifiant (R) étant entièrement déterminée par la donnée de u₀ et u₁, il suffit de prouver que l’on peut toujours trouver λ et μ solutions du système

$\begin{cases} \lambda + \mu = u_0 \\ \lambda r_1 + \mu r_2 = u_1 \end{cases}$

Or ce système a pour déterminant r₂ − r₁ non nul. Il est donc toujours possible d’exprimer une suite vérifiant (R) comme combinaison linéaire des suites $(r_1^n)_{n \in \mathbb N}$ et $(r_2^n)_{n \in \mathbb N}$

Cette situation se produit pour toute suite à valeurs réelles pour laquelle le discriminant $\Delta = a^2 + 4b\,$ est strictement positif, ou pour toute suite à valeurs complexes pour laquelle le discriminant est non nul.

Si le polynôme possède une racine double

Si le discriminant est nul, le problème est tout autre car on ne trouve qu’une seule valeur r₀, donc une seule famille de suites géométriques $(\lambda r_0^n)_{n \in \mathbb N}$ vérifiant (R) . L’idée consiste alors à rechercher les suites $(\lambda_n)_{n \in \mathbb N}$ telles que, pour tout entier n, $u_n = \lambda_n r_0^n$ avec $(u_n)_{n \in \mathbb N}$ vérifiant (R). Cette méthode s’appelle la méthode de variation de la constante. On s’assure d’abord de l’existence de la suite $(\lambda_n)_{n \in \mathbb N}$ en vérifiant que r₀ n’est jamais nul . La relation de récurrence sur $(u_n)_{n \in \mathbb N}$ se traduit par une relation de récurrence sur $(\lambda_n)_{n \in \mathbb N}$ :

$r_0^2\lambda_{n+2} =ar_0\lambda_{n+1} + b\lambda_n$

En utilisant ensuite le fait que a² + 4b = 0 et que $r_0 = \dfrac{a}{2}$, on obtient la relation caractéristique de toute suite arithmétique :

λ_{n + 2} − λ_{n + 1} = λ_{n + 1} − λ_n

La suite $(\lambda_n)_{n \in \mathbb N}$ est donc une suite arithmétique de terme général

λ_n = λ + μn.

Les suites $(u_n)_{n \in \mathbb N}$ vérifiant (R) ont alors pour terme général :

$u_n =(\lambda + \mu n)r_0^n$.

Ce résultat s'applique pour des suites à valeurs réelles ou complexes pour lesquelles le discriminant du polynôme caractéristique est nul.

Si le polynôme ne possède pas de racine réelle

C'est le cas pour les suites à valeurs réelles pour lesquelles le discriminant du polynôme caractéristique est strictement négatif. L’équation du second degré possède alors dans $\mathbb C$ deux racines conjuguées.

$r_1= \rho e^{i\theta}\,$ et $r_2= \rho e^{-i\theta}\,$.

Les suites de terme général $A\rho^n e^{in\theta} + B\rho^n e^{-in\theta}\,$ sont des suites complexes vérifiant (R). Parmi celles-ci, celles pour lesquelles A et B sont conjugués, sont des suites réelles . Donc les suites de terme général

$u_n = (\lambda \cos(n\theta) + \mu \sin(n\theta))\rho^n \,$

sont des suites réelles vérifiant (R) (on a pris A = λ / 2 − iμ / 2). A-t-on alors trouvé toutes les suites vérifiant (R) ? Une suite vérifiant (R) étant entièrement déterminée par la donnée de u₀ et u₁, il suffit de prouver que l’on peut toujours trouver λ et μ solutions du système

$\begin{cases} \lambda = u_0 \\ \lambda \rho \cos(\theta)+ \mu \rho \sin(\theta) = u_1 \end{cases}$

Or ce système a pour déterminant ρsin(θ) non nul. Il est donc toujours possible d’exprimer une suite vérifiant (R) comme combinaison linéaire des suites $(\rho^n\cos(n\theta))_{n \in \mathbb N}$ et $(\rho^n\sin(n\theta))_{n \in \mathbb N}$.

Suite récurrente d’ordre p

Sous-espace vectoriel de dimension p

Si on appelle (R_p) la relation de récurrence :

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

et si on appelle $E_{R_p}$, l’ensemble des suites à valeurs dans 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 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 $K^p\,$ : à chaque suite (u) de $E_{R_p}$, on associe le p_uplet $(u_0, u_1, \cdots,u_{p-1})$. Il suffit alors de connaître une famille libre de p suites vérifiant (R_p), l’ensemble $E_{R_p}$ est alors engendré par cette famille libre.

Terme général

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 $(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}$

Le terme général de la suite U est alors déterminé par

U_n = AⁿU₀

Le problème semble alors terminé. Mais la réelle difficulté consiste alors à calculer Aⁿ... On préfère plutôt déterminer une base de $E_{R_p}$.

Recherche d'une base

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

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_iId)^{\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_iId)^{\alpha_i}$ pour peu que le degré de Q soit inférieur strictement à α_i. Cette démonstration se fait par récurrence sur α_i. Comme les suites $(n^jr_i^n)_{n \in \mathbb N}$, pour j = 0 à α_i − 1 forment une partie libre de α_i éléments, la famille de toutes les suites $(n^jr_i^n)_{n \in \mathbb N}$, pour j = 0 à α_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 de suites dont le terme général est $Q(n)r_i^n$ avec degré de Q strictement inférieur à α_i.

Retour à la récurrence d'ordre 2

Si le polynôme caractéristique se scinde en (X − r₁)(X − r₂) alors les polynômes Q sont de degré 0 et les éléments de $E_{R_2}$ sont des suites dont le terme général est $\lambda_1r_1^n + \lambda_2r_2^n$.

Si le polynôme caractéristique se scinde en (X − r₀)² alors les polynômes Q sont de degré 1 et les éléments de $E_{R_2}$ sont des suites dont le terme général est $(\lambda_1n +\lambda_2)r_0^n$.

Ce document provient de « Suite r%C3%A9currente lin%C3%A9aire ».