Suites récurrentes linéaires : énoncé (MP)
Suites récurrentes linéaires
Soit $a_0,\dots,a_{p-1}\in\mathbb K$ et $S$ l'ensemble des suites $(u_n)\in\mathbb K^{\mathbb N}$ telles que $$\forall n\in\mathbb N,\quad u_{n+p}=a_{p-1}u_{n+p-1}+\cdots+a_1u_{n+1}+a_0u_n.$$ Soit $P=X^p-a_{p-1}X^{p-1}-\cdots-a_1X-a_0$ le polynôme caractéristique de la relation. Si $P$ est scindé à racines simples $r_1,\dots,r_p$ sur $\mathbb K$, les suites de $S$ sont exactement les suites $u_n=\sum_{i=1}^pc_ir_i^n$, $(c_1,\dots,c_p)\in\mathbb K^p$ (avec la convention $0^0=1$).
Démonstration : Suites récurrentes linéaires
Preuve
$S$ est un sous-espace vectoriel de $\mathbb K^{\mathbb N}$, et $(u_n)\mapsto(u_0,\dots,u_{p-1})$ est un isomorphisme de $S$ sur $\mathbb K^p$ : une suite de $S$ est déterminée par ses $p$ premiers termes, qui sont arbitraires. Donc $\dim S=p$.
Pour $(u_n)\in S$, on pose $U_n=(u_n,u_{n+1},\dots,u_{n+p-1})^\top$. Alors $U_{n+1}=MU_n$ avec $$M=\begin{pmatrix}0&1&0&\cdots&0\\0&0&1&\ddots&\vdots\\\vdots&&\ddots&\ddots&0\\0&\cdots&\cdots&0&1\\a_0&a_1&\cdots&\cdots&a_{p-1}\end{pmatrix}.$$ $M$ est la transposée de la matrice compagnon de $P$ (les coefficients de $P$ sont les $-a_k$, d'où la dernière colonne $(a_0,\dots,a_{p-1})$ de $C_P$), donc $\chi_M=\chi_{C_P}=P$. $P$ étant scindé à racines simples, $M$ est diagonalisable : $M=QDQ^{-1}$ avec $D=\mathrm{diag}(r_1,\dots,r_p)$. Alors $U_n=M^nU_0=QD^nQ^{-1}U_0$, et la première coordonnée $u_n$ est combinaison linéaire, à coefficients indépendants de $n$, des $r_i^n$.
Les $p$ suites $(r_i^n)_n$ appartiennent à $S$, car $P(r_i)=0$ donne $r_i^{n+p}=\sum_{k=0}^{p-1}a_kr_i^{n+k}$, et elles engendrent $S$. Comme $\dim S=p$, elles en forment une base.
Une récurrence d'ordre 2
Soit $u_0=0$, $u_1=1$ et $u_{n+2}=u_{n+1}+2u_n$. Le polynôme $X^2-X-2=(X-2)(X+1)$ a deux racines simples, donc $u_n=c_12^n+c_2(-1)^n$. Les conditions initiales donnent $c_1+c_2=0$ et $2c_1-c_2=1$, soit $c_1=\frac13$ et $c_2=-\frac13$ : $$u_n=\frac{2^n-(-1)^n}{3}.$$ Contrôle : la formule donne $u_2=1$ et $u_3=3$, conformes à la relation ($u_2=1+0$, $u_3=1+2$).
Racines multiples
Si $P$ a des racines multiples, $M$ n'est pas diagonalisable : pour tout $\lambda$, les $p-1$ premières lignes de $M-\lambda I_p$ sont libres, donc chaque sous-espace propre est une droite. Les sous-espaces caractéristiques montrent alors qu'une base de $S$ est formée des suites $(n^jr^n)_n$, $0\leq j<m_r$, pour chaque racine $r$ de multiplicité $m_r$. Le cas $p=2$ avec racine double, $u_n=(\alpha+\beta n)r^n$, est au programme de première année ; le cas général est à savoir retrouver.