É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

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 sur $\mathbb{C}$ .

Notons $r_1,\ldots,r_k$ les racines (réelles ou complexes) de l'équation caractéristique associée 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 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

conditions particulières, il suffit de calculer ses coefficients $\lambda_{i,j}$ en résolvant un système linéaire ordinaire, de

équations à

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

(racine simple) et

(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

, 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

. On obtient :

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