É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}$ :

$\displaystyle ({\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 :

$\displaystyle (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 :

$\displaystyle 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 :

$\displaystyle ({\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 :

$\displaystyle (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 :

$\displaystyle 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.

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

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

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


         © UJF Grenoble, 2011                              Mentions légales