Suite récurrente linéaires
Définition
On dira que \( U\) est une suite de \( \R^n\) pour un certain \( n\in \N_{{>}0}\) si pour tout entier \( k\in\N\) , \( U_k\in\R^n\) .
Le cas bien connu est celui des suites réelles (c'est à dire \( n=1\) ). Dans ce cas, il a été étudié le cas des suites récurrentes et explicites ainsi que le cas particulier des suites géométriques. Nous avions les résultats suivants :
Définition
Une suite \( u\) de \( \R\) sera dite géométrique si il existe un nombre \( q\in\R\) tel que pour tout \( n\in \N\) , \( u_{n+1}=qu_{n}\) .
Le nombre \( q\) est appelé la raison de la suite.
A l'aide d'un raisonnement par récurrence on a le résultat suivant.
Proposition
Soit \( u\) une suite géométrique de raison \( q\) alors pour tout entier \( n\in \N\) , \[u_n=q^nu_0\]
On peut faire la même chose dans \( \R^n\) .
Définition
On dira qu'une suite \( U\) de \( \R^n\) est géométrique si il existe une matrice \( Q\in\M_n{\R}\) tel que \[U_{n+1}=QU_n\]
Toujours par récurrence, avec pratiquement la même preuve, on arrive au (même) résultat suivant.
Proposition
Soit \( u\) une suite géométrique de \( \R^n\) de raison \( Q\) alors pour tout entier \( k\in \N\) , \[U_k=Q^kU_0\]
Appliquons ce principe au suite multi-récurrente.
Définition
On dira qu'une suite \( u\) de \( \R\) est récurrente linéaire d'ordre \( n\) pour un certain entier \( n\in \N_{{>}0}\) s'il existe des réel \( (a_i)_{i\in[\![0 ; n-1]\!]}\) tel que pour tout \( k\in\N\)
\[u_{k+n}=\sum_{i=0}^{n-1}a_{i}u_{k+i}\]
On dit que \( (a_0, a_1, \ldots, a_{n-1})\) est la raison de cette suite récurrente linéaire.
Le cas bien connu est celui des suites récurrente linéaire d'ordre \( 1\) qui vérifie donc par définition \( u_{k+1}=a_0u_k\) . Le nombre réel \( a_0\) est donc la raison de la suite géométrique.
Une suite d'ordre \( 2\) est de la forme \( u_{k+2}=a_0u_k+a_{1}u_{k+1}\) . La plus célèbre est la suite de Fibonacci :
\[u_{k+2}=u_k+u_{k+1}\]
où \( u_0=0\) et \( u_1=1\) .
Définition
Soit \( u\) une suite récurrente linéaire d'ordre \( n\) de raison \( (a_0, \ldots, a_{n-1})\) . On appel matrice compagnon de \( u\) , notée \( \mathcal{Co}mpa(a_0, \ldots, a_{n-1})\) ou \( \mathcal{Co}mpa(u)\) , la matrice de \( \M_n{\R}\)
\[\mathcal{Co}mpa(a_0, \ldots, a_{n-1}) =
\begin{pmatrix}
0 & 1 & 0 & \cdots & 0 \\
0 & 0 & 1 & \ddots & \vdots \\
\vdots & & & \ddots & 0 \\
0 & \cdots & &0&1\\
a_0 & a_1&\cdots &a_{n-2} & a_{n-1}
\end{pmatrix}
\]
La matrice compagnon de la suite de Fibonacci est
\( \begin{pmatrix}
0&1\\
1&1
\end{pmatrix}
\)
Proposition
Soit \( u\) une suite récurrente linéaire d'ordre \( n\) . Notons \( U\) la suite de \( \R^n\) où pour tout \( k\in \N\) ,
\( U_k=\begin{pmatrix}
u_k\\
u_{k+1}\\
\vdots\\
u_{k+{n-1}}
\end{pmatrix}\) .
Alors pour tout \( k\in\N\) \[U_k=\mathcal{Co}mpa(u)^nU_0\].
Démonstration
Si \( (a_0, \ldots, a_{n-1})\) désigne la raison de \( u\) alors
on a \[U_{k+1}=
\begin{pmatrix}
u_{k+1}\\
\vdots\\
u_{k+{n-1}}\\
u_{k+{n}}
\end{pmatrix}
=
\begin{pmatrix}
u_{k+1}\\
\vdots\\
u_{k+{n-1}}\\
a_0u_k+a_1u_{k+1}+\cdots+a_{n-1}u_{k+{n-1}}
\end{pmatrix}
=
\mathcal{Co}mpa(u)U_0
\]
Ainsi \( U\) est une suite géométrique de \( \R^n\) et vérifie donc \( U_k=\mathcal{Co}mpa(u)^nU_0\) .
La difficulté réside donc dans le calcul de \( \mathcal{Co}mpa(u)^n\) ; problème partiellement réglé par les outils d'algèbre des paragraphes précédents.
Nous avons cependant besoin de déterminer le polynôme caractéristique de la matrice compagnon.
Proposition
Soit \( u\) une suite récurrente linéaire d'ordre \( n\) de raison \( (a_0, \ldots, a_{n-1})\) . Alors \( \chi_{\mathcal{Co}mpa(u)}(X)\) le polynôme caractéristique de la matrice compagnon est
\[\chi_{\mathcal{Co}mpa(u)}(X)=(-1)^{n+1}\left(-X^n+\sum_{i=0}^{n-1}a_iX^i\right)\]
Démonstration
Notons \( P_{a_0, \ldots, a_{n-1}}(X)=\chi_{\mathcal{Co}mpa(a_0, \ldots, a_{n-1})}(X)\)
En développant suivant la première colonne on montre sans peine que \[P_{a_0, \ldots, a_{n-1}}(X)=-X P_{a_1, \ldots, a_{n-1}}(X)+(-1)^{n+1}a_0\]
Exactement de la même manière on montre que
\[P_{a_1, \ldots, a_{n-1}}(X)=-XP_{a_2, \ldots, a_{n-1}}(X)+(-1)^{n}a_1\]
En injectant cette égalité dans la première on arrive à
\begin{eqnarray*}
P_{a_0, \ldots, a_{n-1}}(X)&=&-X P_{a_1, \ldots, a_{n-1}}(X)+(-1)^{n+1}a_0\\
&=&-X \left(-XP_{a_2, \ldots, a_{n-1}}(X)+(-1)^{n}a_1\right)+(-1)^{n+1}a_0\\
&=&(-X)^2P_{a_2, \ldots, a_{n-1}}(X)+(-1)^{n}(-X)a_1+(-1)^{n+1}a_0\\
&=&(-X)^2P_{a_2, \ldots, a_{n-1}}(X)+(-1)^{n+1}Xa_1+(-1)^{n+1}a_0\\
\end{eqnarray*}
En itérant ce processus on arrive à
\[P_{a_0, \ldots, a_{n-1}}(X)=(-X)^{n-1}P_{a_{n-1}}(X)+(-1)^{n+1}a_{n-2}X^{n-2}+\cdots+(-1)^{n+1}Xa_1+(-1)^{n+1}a_0\]
or \( P_{a_{n-1}}(X)=det(a_{n-1}-X)=a_{n-1}-X\) . On arrive alors
\begin{eqnarray*}
P_{a_0, \ldots, a_{n-1}}(X)&=&(-X)^{n-1}(a_{n-1}-X)+(-1)^{n+1}a_{n-2}X^{n-2}+\cdots+(-1)^{n+1}Xa_1+(-1)^{n+1}a_0\\
&=&(-X)^{n-1}a_{n-1}+(-X)^n+(-1)^{n+1}a_{n-2}X^{n-2}+\cdots+(-1)^{n+1}Xa_1+(-1)^{n+1}a_0\\
&=&(-1)^{n+1}\left(-X^n+a_{n-1}X^{n-1}+a_{n-2}X^{n-2}+\cdots+a_1X^1+a_0X^0\right)
\end{eqnarray*}
Corollaire
Si l'équation \( \dpl{-X^n+\sum_{i=0}^{n-1}a_iX^i}=0\) admet \( n\) solutions \( \lambda_1, \ldots, \lambda_n\) alors la suite récurrente linéaire de raison \( (a_0, \ldots, a_{n-1})\) s'écrit pour tout \( k\in\N\)
\[u_k=\alpha_1\lambda_1^k+\alpha_2\lambda_2^k+\cdots+\alpha_n\lambda_n^k\]
Démonstration
Si il existe \( n\) solutions au polynôme caractéristique alors la matrice est diagonalisable. Dans une certaine base la matrice est \( \begin{pmatrix}
\lambda_1&0&&&0\\
0&\lambda_2&0&&0\\
&&&\ddots&0\\
0&&&0&\lambda_n
\end{pmatrix}\) dont la puissance \( k\) -ème donne
\( \begin{pmatrix}
\lambda_1^k&0&&&0\\
0&\lambda_2^k&0&&0\\
&&&\ddots&0\\
0&&&0&\lambda_n^k
\end{pmatrix}\)
Or on sait que \( U_k=\mathcal{Co}mpa(u)^nU_0\) . Puisque le changement de base correspond à une somme linéaire de ces puissances, le résultat est prouvé.
Par exemple, pour la suite de Fibonacci, \( u_{k+2}=u_k+u_{k+1}\) .
On considère l'équation \( -X^2+X+1=0\) qui admet deux solutions \( \lambda_1=\dfrac{1-\sqrt{5}}{2}\) et \( \lambda_2=\dfrac{1+\sqrt{5}}{2}\) . Alors
\( u_k=\alpha\left(\dfrac{1-\sqrt{5}}{2}\right)^k+\beta\left(\dfrac{1+\sqrt{5}}{2}\right)^k\) . Puisqu'on sait que \( u_0=0\) et \( u_1=1\) on en déduit les deux équations suivantes :
\[
\left\{
\begin{array}{rcl}
\alpha\left(\dfrac{1-\sqrt{5}}{2}\right)^0+\beta\left(\dfrac{1+\sqrt{5}}{2}\right)^0&=&0\\
\alpha\left(\dfrac{1-\sqrt{5}}{2}\right)^1+\beta\left(\dfrac{1+\sqrt{5}}{2}\right)^1&=&1
\end{array}
\right.
\Longleftrightarrow
\left\{
\begin{array}{rcl}
\alpha+\beta&=&0\\
\alpha\dfrac{1-\sqrt{5}}{2}+\beta\dfrac{1+\sqrt{5}}{2}&=&1
\end{array}
\right.
\]
On trouve \( \alpha=-\dfrac{1}{\sqrt{5}}\) et \( \beta=\dfrac{1}{\sqrt{5}}\) pour avoir finalement
\[\forall k \in \N, \quad u_k=\dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^k-\left(\dfrac{1-\sqrt{5}}{2}\right)^k\right)\]
Autre exemple : on considère la suite récurrente linéaire d'ordre \( 3\) définie pour tout \( k\in\N\) par
\( u_{k+3}=2u_{k+2}+u_{k+1}-2u_k\) avec \( u_0=0\) , \( u_1=1\) et \( u_2=3\) . On considère l'équation \( X^3=2X^2+X-2\) qui équivaut à \( X^3-2X^2-X+2=0\) soit encore \( X^2(X-2)-(X-2)=0\) soit encore \( (X^2-1)(X-2)=0\) dont les solutions sont \( -1\) , \( 1\) et \( 2\) . Alors
\( u_k=a(-1)^k+b(1)^k+c(2)^k\) . Les conditions initiales permettent de donner le système suivant :
\[
\left\{
\begin{array}{rcccl}
0&=&u_0&=&a+b+c\\
1&=&u_1&=&-a+b+2c\\
3&=&u_2&=&a+b+4c
\end{array}
\right.
\]
dont la seule solution est \( a=0\) , \( b=-1\) et \( c=1\) . Finalement pour tout \( k\in \N\) ,
\[u_k=2^k-1\]
