\documentclass[11pt]{amsart}
\usepackage[theo]{kbexo}

\def\ft#1#2{{#1}^{\underline{#2}}}
\DeclareMathOperator{\cd}{cd}
\def\O{\mathcal{O}}
\def\S{\mathcal{S}}

\begin{document}
\agregtitle{Équations de récurrence linéaire}

\section{Introduction}

Dans ce texte, on s'intéresse aux suites vérifiant une équation de récurrence
linéaire. Le paragraphe~2 étudie théoriquement l'ensemble des solutions d'une
telle équation, et en particulier sa dimension. Les paragraphes~3 et 4 sont
algorithmiques et se rapportent aux équations dont les coefficients sont
polynomiaux. Le paragraphe~3 donne un algorithme pour en trouver les
solutions polynomiales, et le paragraphe~4 un algorithme pour en trouver les
solutions hypergéométriques, dans le cas où l'équation considérée est
homogène.

\section{L'anneau des suites}

Soit $K$ un corps de caractéristique nulle. On note $K^\NM$ l'ensembles des
suites $(a(n))_{n\in\NM}$ dont les termes appartiennent à $K$. Muni de
l'addition et de la multiplication terme à terme, $K^\NM$ est un anneau. C'est
aussi un $K$-espace vectoriel, et donc une $K$-algèbre. Cette algèbre n'est
pas intègre.

On définit l'opérateur \emph{shift} $N$ en posant, pour toute suite $y$ de
$K^{\NM}$, $Ny(n)=y(n+1)$. L'opérateur $N$ et ses puissances sont des
applications linéaires sur $K^\NM$.

On appelle opérateur de récurrence linéaire sur $K^\NM$ un opérateur de la
forme
$$L=\sum_{k=0}^ra_kN^k,$$
où les $a_k$ sont des éléments de $K^\NM$. si $a_0$ et $a_r$ sont non nuls,
l'ordre de $L$ est ord $L=r$. Une équation de récurrence linéaire dans $K^n$
est une équation de la forme
$$Ly=f,$$
où $L$ est un opérateur de récurrence linéaire et où $f$ est un élément de
$K^\NM$. Si $f=0$, une telle équation est dite homogène. L'ensemble des
solutions de $Ly=0$ est un sous-espace vectoriel de $K^\NM$ et l'ensemble des
solutions de $Ly=f$ un sous espace affine de $K^\NM$.

Un parallèle avec la théorie des équations différentielles pousse à espérer
que l'espace des solutions d'une telle équation est de dimension $r$. Il n'en
est rien, comme le montrent les exemples suivants.

\medskip

\misctitle{Exemple 1} Soient $a=(1,0,1,0,\dots)$, $b=(0,1,0,1,\dots)$ et
$L=aN+b$. Alors l'ensemble des solutions de $Ly=0$ est de dimension infinie.

\misctitle{Exemple 2} Si maintenant $L=aN-1$, l'ensemble des solutions de
$Ly=0$ est réduit à $\{0\}$.

\misctitle{Exemple 3} Soient $p(n)=(n-1)(n-4)(n-7)$, $q(n)=n(n-3)(n-6)$ et
$L=pN-q$. Alors l'ensemble des solutions de $Ly=0$ est de dimension $4$,
engendré par $(1,0,0,0,\dots)$, $(0,0,1,4/5,0,0,\dots)$,
$(0,0,0,0,0,1,5/4,0,0,0,\dots)$ et la suite $y$ telle que
$y(n)=(n-1)(n-4)(n-7)$.

\medskip

On essaie d'établir un cadre où la dimension de l'espace solution serait
l'ordre de l'équation de récurrence. Dans les deux premiers exemples donnés,
la suite $a$ contient une infinité de $0$. On éliminera ce cas. Dans le
troisième exemple, trois des éléments de la base donnée n'ont qu'un nombre
fini de termes non nuls. Cela suggère d'identifier de telles suites à $0$.

Ainsi, on définit $\S(K)$ comme le quotient de $K^\NM$ par la relation
d'équivalence $\sim$ sur $K^\NM$ définie par $a\sim b$ s'il existe $n_0$ dans
$\NM$ tel que $a(n)=b(n)$ pout tout $n$ supérieur à $n_0$. Cela revient en
fait à poser $\S(K)=K^\NM/J,$ où
$$J=\bigcup_{k=0}^\infty\ker N^k.$$
Grâce au théorème de factorisation des applications linéaires, on peut voir
qu'il existe un unique automorphisme $E$ de $\S(K)$ tel que $\varphi
N=E\varphi$, où $\varphi$ désigne la projection canonique de $K^\NM$ dans
$\S(K)$. Par souci de simplification, on écrira $N$ pour $E$ et $a$ à la
place de sa classe $a+J$, pour toute suite $a$ de $K^\NM$.

\begin{prop}
Un élément non nul de $\S(K)$ est inversible si et seulement s'il n'est pas
un diviseur de $0$. Un tel élément est alors aussi appelé unité de $\S(K)$.
\end{prop}
On peut maintenant démontrer que les équations de récurrence linéaire sur
$\S(K)$ ont la propriété recherchée.

\begin{theo}
Soit $L=\sum_{k=0}^ra_kN^k$ un opérateur de récurrence
linéaire d'ordre $r$ sur $\S(K)$. Si $a_0$ et $a_r$ sont
des unités de $\S(K)$, alors $\dim\ker L=r$.
\end{theo}
\begin{proof}
Montrons d'abord que $\dim\ker L\leq r$. Pour cela, on considère $r+1$
éléments $y_1,\dots,y_{r+1}$ de $\ker L$. On va montrer que ces éléments sont
nécessairement linéairement dépendants. Comme $Ly_i=0$ pour tout $i$, alors
il existe un entier $n_0$ tel que pour tout $n\geq n_0$,
$$\sum_{k=0}^ra_k(n)y_i(n+k)=0$$
pour tout $i$. Soit $Y(n)$ l'élément de $K^{r+1}$ égal à
$(y_1(n),\dots,y_{r+1}(n))$ pour tout $n$ de $\NM$. Soient $\L_n$ l'espace
vectoriel engendré par $Y(n),\dots,Y(n+r-1)$ et 
$$\O_n=
\set{(u_1,\dots,u_{r+1})\in K^{r+1}\colon \sum_{i=1}^{r+1}u_iv_i=0, \forall
(v_1,\dots,v_{r+1})\in\L_n}.$$ Alors $\O_n$ est un sous espace vectoriel de
$K^{r+1}$ tel que $1\leq\dim\O_n\leq r+1$ pour tout $n$. Comme $a_0$ est une
unité, il existe un entier $M$ tel que $a_0(n)\ne0$ pour tout $n$ supérieur
ou égal à $M$. Soit $j=\max\{n_0,M\}$. Pour tout $n$ supérieur ou égal à $j$,
$$y_i(n)=-\sum_{k=1}^r\frac{a_k(n)}{a_0(n)}y_i(n+k)$$
pour tout $i$. Donc, si $n\geq j$, $Y(n)$ appartient à $\L_{n+1}$. Il suit
que $\L_n\subset\L_{n+1}$ et que $\O_{n+1}\subset\O_n$ dès que $n\geq j$.
Ainsi, la suite $(\O_n)_{n\geq j}$ est une suite décroissante d'espaces
vectoriels de dimensions finies et supérieures ou égales à $1$. On peut alors
démontrer que l'intersection de ces espaces vectoriels est non triviale, ce
qui implique que les $y_i$ sont linéairement dépendants.

Montrons maintenant que $\dim\ker L\geq r$. On va pour cela exhiber une
famille de $r$ éléments linéairement indépendants de $\ker L$. Comme $a_0$ et
$a_r$ sont des unités, il existe $n_0$ dans $\NM$ tel que $a_0(n)$ et $a_r(n)$
sont non nuls pour tout $n\geq n_0$. Soit $v(0),\dots,v(r-1)$ une base de
$K^r$, où $v(j)=(v_1(j),\dots,v_{r}(j))$ pour tout $j$ dans
$\set{0,\dots,r-1}$. On définit $y_1,\dots,y_r$ dans $\S(K)$ en posant, pour
tout $i$ dans $\set{1,\dots,r}$: $y_i(n_0+j)=v_i(j)$ pour tout $j$ dans
$\{0,\dots,r-1\}$ et
$$y_i(j) = -\sum_{k=0}^{r-1}\frac{a_k(j-r)}{a_r(j-r)}y_i(j-r+k),
\quad\text{pour $j\geq n_0+r$}.$$
Pour tout $n$ de $\NM$, on pose $Y(n)=(y_1(n),\dots,y_r(n))$, $\L_n$ l'espace
vectoriel engendré par $Y(n),\dots,Y(n+r-1)$, et
$\O_n=\{u=(u_1,\dots,u_{r})\in K^{r}\colon \sum_{i=1}^{r}u_iw_i=0\ \forall
w=(w_1,\dots,w_{r})\in\L_n\}$. Alors $\L_{n_0}=K^r$ et donc $\O_{n_0}=\{0\}$.
Or, comme précédemment, $\O_{n+1}\subset\O_n$ pour tout $n\geq n_0$. On en
déduit que les $y_i$ sont linéairement indépendants.
\end{proof}
\begin{defi}
Une suite $a$ de $\S(K)$ est dite polynomiale sur $K$ s'il existe un polynôme
$p$ dans $K[x]$ tel que $a(n)=p(n)$ pour presque tout $n$ de $\NM$
(c'est-à-dire~: l'ensemble des éléments $n$ de $\NM$ tels que $a(n)\ne p(n)$
est fini). Elle est dite rationnelle sur $K$ s'il existe une fonction
rationnelle $r$ de $K(x)$ telle que $a(n)=r(n)$ pour presque tout $n$ de
$\NM$. Elle est dite hypergéométrique sur $K$ s'il existe des suites $p$ et
$q$ polynomiales sur $K$ telles que $pNa+qa=0$.
\end{defi}
\noindent Toute suite polynomiale est rationnelle, et toute suite rationnelle
non nulle est hypergéométrique. De plus, toute suite rationnelle non nulle
est une unité.

\begin{prop}
Soient $a$ et $y$ des éléments de $\S(K)$ tels que $y\ne0$ et $Ny=ay$. Alors
$a$ et $y$ sont des unités.
\end{prop}

\begin{coro}
Toute suite hypergéométrique est une unité.
\end{coro}

\section{Solutions polynomiales}

Ce paragraphe donne un algorithme qui donne toutes les solutions polynomiales
d'une équation $Ly=f$ à coefficients polynomiales. C'est-à-dire:
$$L=\sum_{i=0}^rp_i(n)N^i,$$
où les $p_i$ sont des suites polynomiales sur $K$ et où $p_0$ et $p_r$ sont
non nulles. Alors, pour que cette équation ait des solutions polynomiales, la
suite $f$ doit également être polynomiale. On le suppose donc dans la suite
du paragraphe.

On peut résoudre ce problème en trouvant d'abord une borne supérieure $B$
pour le degré de polynômes solutions de l'équation, puis en décrivant les
polynômes solutions qui ont un degré inférieur à $B$ par la méthode des
coefficients indéterminées..

\medskip

Pour obtenir $B$, on réécrit $L$ en termes de $\Delta=N-1$. On obtient
$$L=\sum_{j=0}^rq_j\Delta^j,\quad\text{où}\quad q_j
  =\sum_{i=j}^r\binom{i}{j} p_i.$$
Soit $y=\sum_{k=0}^da_kn^k$ (où $a_d\ne0$ et où les $a_k$ sont dans $K$) une
solution. On note $\ft{k}{j}$ la "factorielle tombante"
$\ft{k}{j}=k(k-1)\dots(k-j+1)$. Alors le coefficient dominant de
$q_j\Delta^jy(n)$ est égal à cd$(q_j)a_d\ft{d}{j}$. Soit
$$b=\max_{0\leq j\leq r}(\deg q_j-j).$$
Alors $\deg Ly(n)\leq d+b$. Si $d+b<0$, alors $d\leq-b-1$. Sinon, le
coefficient de $n^{d+b}$ dans $Ly(n)$ est
$$a_d\sum_j\hbox{cd}(q_j)\ft{x}{j},$$
où la somme est prise sur l'ensemble $\mathcal E$ des entiers $j$ tels que
$0\leq j\leq r$ et $\deg q_j-j=b$. Si $\deg Ly(n)=d+b$, alors $d+b=\deg f$.
Sinon, le coefficient de $n^{d+b}$ s'annule, et donc $d$ est une racine du
polynôme
$$\alpha(x)=\sum_{i\in\mathcal E}\cd(q_j)\ft{x}{j}.$$
On obtient donc le résultat suivant.

\begin{prop}
Soit $y$ est une solution polynomiale de l'équation $Ly=f$. Soit $d_1$ la plus grande
solution entière de l'équation $\alpha(x)=0$ (si cette
équation
n'a pas de solution entière, $d_1=-\infty$). Alors
$$\deg y\leq\max\{\deg f-b,-b-1,d_1\}.$$
\end{prop}


\section{Solutions hypergéométriques}
Soit $F$ un corps de caractéristique nulle et $K$ une extension de $F$. Étant donnée
un opérateur de récurrence linéaire $L$ à coefficients polynomiaux sur $F$, on cherche
les solutions de l'équation
\begin{equation}\label{EqHomo}
Ly=0
\end{equation}
qui sont hypergéométriques sur $K$. On va ici décrire une méthode pour les équations
d'ordre $2$, qui se généralise aux ordres supérieurs. Nous utiliserons le théorème suivant.

\begin{theo}\label{gosper}
Soit $r$ une fonction rationnelle non nulle sur $K$. Alors il existe
des polynômes $a,b,c$ de $K[x]$ tels que $b$ et $c$ sont unitaires et
$$r(x)=\frac{a(x)}{b(x)}\frac{c(x+1)}{c(x)},$$
où
\begin{enumerate}
\item $\hbox{pgcd}(a(x),b(x+h))=1$ pour tout entier positif ou nul $h$,
\item pgcd$(a(x),c(x))=1$,
\item pgcd$(b(x),c(x+1))=1$.
\end{enumerate}
\end{theo}

On considère donc la récurrence

\begin{equation}\label{ordre2}
p(n)y(n+2)+q(n)y(n+1)+r(n)y(n)=0.
\end{equation}
Soit $y$ une solution hypergéométrique de (\ref{ordre2}). Alors il existe une suite
rationnelle $S$ telle que $y(n+1)=S(n)y(n)$. En substituant dans (\ref{ordre2}),
on obtient
$$p(n)S(n+1)S(n)+q(n)S(n)+r(n)=0.$$
On peut écrire
$$S(n)=z\frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)},$$
où $a$, $b$ et $c$ sont unitaires et satisfont aux conditions (1), (2) et (3) du théorème
\ref{gosper}. Alors
\begin{equation}\label{2ordre2}
z^2p(n)a(n+1)a(n)c(n+2)+zq(n)b(n+1)a(n)c(n+1)+r(n)b(n+1)b(n)c(n)=0.
\end{equation}
On peut alors démontrer que $a(n)$ divise $r(n)$ et $b(n+1)$ divise $p(n)$. Cela laisse
un ensemble fini de candidats pour $a(n)$ et $b(n)$~: les facteurs unitaires de $r(n)$
et $p(n-1)$. On peut diviser (\ref{2ordre2}) par $a(n)b(n+1)$. Il vient
\begin{equation}\label{3ordre2}
z^2\frac{p(n)}{b(n+1)}a(n+1)c(n+2)+zq(n)c(n+1)+\frac{r(n)}{a(n)}b(n)c(n)=0.
\end{equation}
Pour déterminer la valeur de $z$, on considère le coefficient dominant du membre
de gauche de cette équation~: $z$ satisfait une équation de degré inférieure ou égale
à $2$. Ainsi, $a$ et $b$ étant donnés, il y a au plus $2$ choix pour $z$. Pour
un choix donné de $a,b,z$, on
utilise l'algorithme du paragraphe précédent pour déterminer les solutions polynomiales $c$
de (\ref{3ordre2}), s'il en existe. Si c'est le cas, et si $c$ est une telle solution, alors
on en déduit une solution hypergéométrique de (\ref{EqHomo}). On trouve ainsi toutes
les solutions hypergéométriques de cette équation.

\medskip

\noindent{\bf Exemple 1.}
La solution générale de l'équation
$$(n-1)y(n+2)-(n^2+3n-2)y(n+1)+2n(n+1)y(n)=0.$$
est égale à $y(n)=C2^n+Dn!$.

\noindent{\bf Exemple 2.}
On peut montrer que
$$y(n)=\sum_{k=0}^n\binom{n}{k}^2\binom{n+k}k^2$$
satisfait la récurrence
$$(n+2)^3y(n+2)-(2n+3)(17n^2+51n+39)y(n+1)+(n+1)^3y(n)=0.$$
Grâce à l'algorithme précédent, on peut montrer que $y(n)$ n'est pas
hypergéométrique.

\noindent{\bf Exemple 3.}
Soit $i(n)$ le nombre d'involutions sur un ensemble de cardinal $n$.
Alors
$$i(n)=i(n-1)+(n-1)i(n-2).$$
Plus généralement, soit $i_r(n)$ le nombre de permutations sur un
ensemble de cardinal $r$ qui ne contient pas de cycles de longueur
strictement supérieure à $r$. Alors
$$i_r(n)=\sum_{k=1}^r\ft{(n-1)}{k-1}\ i_r(n-k).$$
Pour $r\geq2$, le terme $i_r$ n'est pas hypergéométrique.
En particulier,
$$i(n)=\sum_k\frac{n!}{(n-2k)!2^kk!}$$
n'est pas hypergéométrique.


\bigskip

\misctitle{Références}

\begin{itemize}
\item $A=B$, M. Petkov$\check{\hbox{s}}$ek, H. S. Wilf, D. Zeilberger.

\item \emph{Mathématiques concrètes}, R. L. Graham, D. E. Knuth, O. Patashnik.
\end{itemize}


\end{document}
