Équations de récurrence linéaires

Nous présentons ici la généralisation du théorème 8 aux équations d'ordre quelconque.

Considérons l'équation ${\cal E}$ :

$$({\cal E})\qquad \forall n\in\mathbb{N}\;,\quad u_{n+d} = a_0 u_n + a_1 u_{n+1} +\cdots+ a_{d-1} u_{n+d-1}\;.$$

Pour connaître la forme des solutions de $({\cal E})$, il faut résoudre l'équation caractéristique associée :

$$(ECA)\qquad r^d=a_0+a_1r+\cdots+a_{d-1}r^{d-1}\;.$$

C'est la condition pour que $(u_n)=(r^n)$ soit solution de $({\cal E})$. On démontre le résultat suivant, qui généralise le théorème 8.

Théorème 9   L'ensemble des suites complexes solution de $({\cal E})$ est un espace vectoriel de dimension $d$ sur $\mathbb{C}$.

Notons $r_1,\ldots,r_k$ les racines (réelles ou complexes) de l'équation caractéristique associée $(ECA)$ et $m_1,\ldots,m_k$ leurs multiplicités. Toute solution de l'équation $({\cal E})$. s'écrit :

$$u_n = \sum_{i=1}^k \sum_{j=0}^{m_i-1} \lambda_{i,j} n^j (r_i)^n\;,$$ (3)

où les $d$ coefficients $\lambda_{i,j} ,\;i=1,\ldots,k ,\;j=0,\ldots,m_i\!-\!1$ sont réels ou complexes.

En pratique, pour déterminer une solution vérifiant $d$ conditions particulières, il suffit de calculer ses coefficients $\lambda_{i,j}$ en résolvant un système linéaire ordinaire, de $d$ équations à $d$ inconnues. Exemple : Considérons l'équation suivante :

$$({\cal E})\qquad \forall n\in\mathbb{N}\;,\quad u_{n+3} = u_n+u_{n+1}-u_{n+2}\;.$$

L'équation caractéristique associée est :

$$(ECA)\qquad r^3 = 1+r-r^2\;.$$

Elle a pour racines $1$ (racine simple) et $-1$ (racine double). Toute solution de l'équation de récurrence s'écrit donc :

$$u_n = a(1)^n+b(-1)^n+cn(-1)^n\;.$$

Pour trouver la solution qui vérifie $u_0=-1$, $u_1=1$, $u_2=0$, on résout le système suivant.

$$\left\{ \begin{array}{lcr} a+b &=&-1\\ a-b-c&=&1\\ a+b+2c&=&0 \end{array}\right.$$

La solution est $a=1/4$, $b=-5/4$, $c=1/2$. On obtient :

$$u_n = \frac{1}{4} -\frac{5}{4} (-1)^n+\frac{1}{2}n(-1)^n\;.$$