\documentclass[french]{article}
\usepackage{accents}
\usepackage{theorem}
\usepackage{fewfonts}
\usepackage{amsfonts}
\usepackage{babel}
\usepackage{epsf}
\usepackage{amsmath}



\everymath{\displaystyle}

\def\coupe{}
\def\colorpush{}
\def\colorpop{}
\def\color#1#2#3{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\renewcommand{\sectionmark}[1]{%
% \markright {{\ifnum \c@secnumdepth >\z@
%     \thesection. \ \fi
%     #1}}}
%\renewcommand{\@evenhead}{\parbox{\textwidth}{\thepage\hfill\slshape\leftmark\par\vspace{-2mm}\rule{\textwidth}{0.2mm}}}%
%\renewcommand{\@oddhead}{\parbox{\textwidth}{{\slshape\rightmark}\hfill\thepage\par\vspace{-2mm}\rule{\textwidth}{0.2mm}}}%

\setlength{\hoffset}{-10mm}
\setlength{\voffset}{-10mm}
\setlength{\oddsidemargin}{0mm}
\setlength{\marginparwidth}{0mm}
\setlength{\textwidth}{180mm}
\setlength{\textheight}{230mm}



\def\couleurAxiome{\color{0.8}{0.1}{0}}
\def\couleurTheoreme{\color{1.0}{0}{0}}
\def\couleurProposition{\color{0.6}{0}{0.2}}
\def\couleurLemme{\color{0.8}{0.4}{0}}
\def\couleurDefinition{\color{0.2}{0}{0.6}}
\def\couleurCorollaire{\color{0.8}{0.2}{0.2}}
\def\couleurRemarque{\color{0}{0.3}{0}}
\def\couleurExemple{\color{0.2}{0.6}{0.2}}
\def\couleurDemonstration{\color{0.1}{0.3}{0.1}}
\def\couleurChapitre{\color{0.5}{0}{0}}
\def\couleurSection{\color{0.5}{0}{0}}
\def\couleurSousSection{\color{0.5}{0}{0}}



\newtheorem{axio}{Axiome}[section]
\newenvironment{axiome}{\colorpush\couleurAxiome\begin{axio}}
     {\end{axio}\colorpop}


\newtheorem{theo}{Théorème}[section]
\newenvironment{theoreme}{\colorpush\couleurTheoreme\begin{theo}}
     {\end{theo}\colorpop}

\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}{\colorpush\couleurProposition\begin{prop}}
     {\end{prop}\colorpop}

\newtheorem{lem}[theo]{Lemme}
\newenvironment{lemme}{\colorpush\couleurLemme\begin{lem}}
     {\end{lem}\colorpop}

\newtheorem{defi}{Définition}[section]
\newenvironment{definition}{\colorpush\couleurDefinition\begin{defi}}
     {\end{defi}\colorpop}


\newtheorem{corol}[theo]{Corollaire}
\newenvironment{corollaire}{\colorpush\couleurCorollaire\begin{corol}}
     {\end{corol}\colorpop}

{\theorembodyfont{\rmfamily}
\newtheorem{rem}{Remarque}[section]}
\newenvironment{remarque}{\colorpush\couleurRemarque\begin{rem}}
     {\end{rem}\colorpop}

{\theorembodyfont{\rmfamily}
\newtheorem{exemp}{Exemple}[section]}
\newenvironment{exemple}{\colorpush\couleurExemple\begin{exemp}}
     {\end{exemp}\colorpop}

\newenvironment{demonstration}{\colorpush\couleurDemonstration\noindent{\bf Démonstration}\hspace{0.3cm}}
     {\colorpop\vspace{\theorempostskipamount}}
% \newenvironment{exemple}{\noindent{\bf Exemple}\hspace{0.3cm}}{\vspace{\theorempostskipamount}}

\newcommand{\monchapitre}[1]{\colorpush\couleurChapitre\chapter{#1}\colorpop}
\newcommand{\masection}[1]{\coupe\colorpush\couleurSection\section{#1}\colorpop}
\newcommand{\masoussection}[1]{\coupe\colorpush\couleurSousSection\subsection{#1}\colorpop}

\newcommand{\fig}[3]{\mbox{\parbox{#1}{\rule{0cm}{#2}\special{picture #3}}}}
\newcommand{\zoomfig}[4]{{\dimen0=#1 \dimen1=#2
\divide\dimen0 by 1000 \multiply\dimen0 by #4
\divide\dimen1 by 1000 \multiply\dimen1 by #4
\fig{\dimen0}{\dimen1}{#3 scaled #4}}}

\DeclareMathSymbol{\nmatt}{\mathalpha}{AMSb}{'116}
\DeclareMathSymbol{\zmatt}{\mathalpha}{AMSb}{'132}
\DeclareMathSymbol{\rmatt}{\mathalpha}{AMSb}{'122}
\DeclareMathSymbol{\cmatt}{\mathalpha}{AMSb}{'103}
\DeclareMathSymbol{\qmatt}{\mathalpha}{AMSb}{'121}
\DeclareMathSymbol{\umatt}{\mathalpha}{AMSb}{'125}
\newcommand{\nmat}{\ensuremath{\nmatt}}
\newcommand{\zmat}{\ensuremath{\zmatt}}
\newcommand{\rmat}{\ensuremath{\rmatt}}
\newcommand{\cmat}{\ensuremath{\cmatt}}
\newcommand{\qmat}{\ensuremath{\qmatt}}
\newcommand{\U}{\ensuremath{\umatt}}
\newcommand{\Ker}{\mathop{\mathrm{Ker}}}

\newcommand{\ssi}{si et seulement si\ }
\newcommand{\Fr}{\mathop{\mathrm{Fr}}} 
\newcommand{\rg}{\mathop{\mathrm{rg}}}
\newcommand{\Rbar}{\overline{\rmat }}
\newcommand{\evn}{espace vectoriel normé} 
\newcommand{\ev}{espace vectoriel } 
\newcommand{\evs}{espaces vectoriels }
\newcommand{\sev}{sous-espace vectoriel } 
\newcommand{\sevs}{sous-espaces vectoriels }
\newcommand{\Vect}{\mathop{\mathrm{Vect}}}
\renewcommand{\Im}{\mathop{\mathrm{Im}}}
\renewcommand{\Re}{\mathop{\mathrm{Re}}}
\renewcommand{\det}{\mathop{\mathrm{det}}\nolimits}
\renewcommand{\Sp}{\mathop{\mathrm{Sp}}}
\newcommand{\diag}{\mathop{\mathrm{diag}}}
\newcommand{\car}{\mathop{\mathrm{car}}}
\newcommand{\tr}{\mathop{\mathrm{tr}}} 
\newcommand{\Def}{\mathop{\mathrm{Def}}\nolimits}
\newcommand{\Mat}{\mathop{\mathrm{Mat}}\nolimits}
\renewcommand{\S}{\mathcal{S}} 
\newcommand{\B}{\mathcal{B}}
\newcommand{\E}{\mathcal{E}} 
%\newcommand{\F}{\mathcal{F}} 
\newcommand{\Q}{\mathcal{Q}} 
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\NU}[1]{\|#1\|_{\infty }}
\newcommand{\T}{\mathcal{T}} 
\newcommand{\Id}{\mathrm{Id}}
\renewcommand{\P}{\mathcal{P}} 
\newcommand{\I}{\mathcal{I}} 
\newcommand{\comp}{{}^c}
\renewcommand{\t}{{}^t\!}
\newcommand{\variations}[1]{{\large TABLEAU}}
\newcommand{\ch}{\mathop{\mathrm{ch}}\nolimits}
\newcommand{\sh}{\mathop{\mathrm{sh}}\nolimits}
\renewcommand{\th}{\mathop{\mathrm{th}}\nolimits}
\newcommand{\argth}{\arg\th}
\newcommand{\argsh}{\arg\sh}
\newcommand{\argch}{\arg\ch}
\newcommand{\arctg}{\mathop{\mathrm{arctg}}\nolimits}
\newcommand{\tg}{\mathop{\mathrm{tg}}\nolimits}
\newcommand{\cotg}{\mathop{\mathrm{cotg}}\nolimits}
\newcommand{\dpa}[2]{{\partial #1 \over\partial#2}}
\newcommand{\sgn}{\mathop{\mathrm{sgn}}\nolimits}
\newcommand{\grad}{\mathop{\mathrm{grad}}\nolimits}
\newcommand{\Disc}{\mathop{\mathrm{Disc}}\nolimits}
\newcommand{\F}[5]{\vphantom{F}_{#1}F_{#2}\left[\begin{array}{c}#3\\#4\end{array};#5\right]}\par
\newcommand{\product}{\prod}
\def\vi{{\vec{\mathstrut\imath}}} 
\def\vj{{\vec{\mathstrut\jmath}}} 
\def\vk{{\vec{\mathstrut k}}}
\def\dint{\int\!\!\!\int} \def\tint{\int\!\!\!\int\!\!\!\int}
\def\croit{\nearrow} \def\decroit{\searrow}

\title{Séries hypergéométriques: de Soeur Celine à Zeilberger et Petkovsek}
\author{par Denis Monasse, Lycée Louis le Grand, Paris}


\begin{document}
\maketitle

\section{Introduction}

De récents travaux ont fait progresser de manière significative la théorie des suites et séries hypergéométriques. D'une
part ils ont remis à l'honneur l'algorithme de Soeur Celine Fasenmyer (1945) que l'absence d'outils adéquats pour le
mettre en oeuvre avait fait tomber un peu dans l'oubli, d'autre part ils ont complêté les travaux de R.W.Gosper (1975)
qui avait trouvé un algorithme complet pour la sommation indéfinie de suites hypergéométriques. Les artisans de ces
progrès sont essentiellement Marko Petkovsek, Herbert Wilf et Doron Zeilberger qui exposent de manière magistrale
l'essentiel de leurs méthodes dans l'ouvrage \emph{"A=B"} aux éditions A.K.Peters. Ce texte se veut une introduction à
leur livre et après avoir rappelé quelques résultats élémentaires sur les suites hypergéométriques, présentera les deux
algorithmes \emph{anciens} de Soeur Celine et de Gosper, pour ensuite décrire les algorithmes de Zeilberger pour la
construction de récurrences hypergéométriques et de Petkovsek pour la résolution de ces récurrences.

Les méthodes seront illustrées avec le logiciel Maple de Waterloo University en utilisant la bibliothèque EKHAD
développée par un élève de Doron Zeilberger. Le lecteur intéressé trouvera sur les deux sites Web 
\begin{center}\texttt{http://www.cis.upenn.edu/\~{}wilf/AeqB.html}\end{center}
et
\begin{center}\texttt{http://www.math.temple.edu/\~{}zeilberg}\end{center}
les liens nécessaires vers les différentes implémentations Maple, Mathematica ou Axiom de ces algorithmes.

\section{Séries hypergéométriques}
\subsection{Notion de séries hypergéométriques}

\begin{definition} On appelle série hypergéométrique une série $\sum_k t_k$ telle que le
rapport $\frac{t_{k+1}}{t_k}$ soit une fraction rationnelle en $k$, soit
\[\frac{t_{k+1}}{t_k}=\frac{P(k)}{Q(k)},\quad P,Q\in \rmat[X]\]
$Q$ n'ayant pas de racine entière positive.
\end{definition}

\begin{remarque} On dira aussi de manière équivalente que la suite $(t_k)$ est hypergéométrique ou que $t_k$ est
un terme hypergéométrique.
\end{remarque}

\begin{exemple} $t_k=x^k$, $t_k=k!$, $t_k=\frac{(k^2-1)(2k+1)!}{(3k-1)!}$.
\end{exemple}

Supposons les polynômes $P$ et $Q$ scindés. On peut alors écrire de manière unique à l'ordre près
\[\frac{t_{k+1}}{t_k}=\frac{(k+a_1)(k+a_2)\ldots (k+a_p)}{(k+b_1)(k+b_2)\ldots (k+b_q)}\frac{x}{k+1}\]
où $x$ est une constante (le $k+1$ résulte d'une longue tradition liée à la présence fréquente d'un $k!$ au
dénominateur de $t_k$). Si l'on impose à
$t_0$ de valoir 1, la série est entièrement déterminée par la donnée de $a_1,\ldots ,a_p,b_1,\ldots ,b_q$. On la
note alors
\[\F{p}{q}{a_1,\ldots ,a_p}{b_1,\ldots b_q}{x}\]

\begin{exemple} La série exponentielle est simplement la série $\F{0}{0}{-}{-}{x}$, la série $\sum_k
\frac{x^k}{(k!)^2}$ est la série $\F{0}{1}{-}{1}{x}$. Maple est capable de reconnaître directement une série
hypergéométrique, comme le montre l'exemple ci dessous:

\begin{verbatim}
> sum(binomial(n,k)^2*x^k/(2*k)!,k=0..infinity);
               hypergeom([-n, -n], [1, 1, 1/2], 1/4 x)
\end{verbatim}
\end{exemple}

\subsection{Suites associées}

L'ensemble des séries hypergéométriques n'est malheureusement pas stable par addition comme le montre l'exemple
de la suite $(2^n+1)_{n\in \nmat }$ qui est la somme de deux suites hypergéométriques sans l'être elle même. Il
est intéressant de décomposer les sommes de séries hypergéométriques d'une manière canonique. Pour cela
introduisons la définition suivante:

\begin{definition} Deux suites  $(s_n)$ et $(t_n)$ sont dites associées si le rapport $s_n/t_n$
est une fraction rationnelle en $n$.
\end{definition}

\begin{remarque} Il s'agit visiblement d'une relation d'équivalence. Toute suite associée à une
suite hypergéométrique est visiblement encore hypergéométrique.\end{remarque}

\begin{proposition}\label{prop0} Soit $(s_n)$ une suite hypergéométrique non constante. Alors la suite
$(s_{n+1}-s_n)$ est une suite hypergéométrique associée.
\end{proposition}

\begin{demonstration} Si $r(n)=s_{n+1}/s_n$, on a $s_{n+1}-s_n=(r(n)-1)s_n$.
\end{demonstration}

\begin{proposition}\label{prop1} Soit $(s_n)$ et $(t_n)$ deux suites hypergéométriques dont la somme n'est pas
nulle. Alors la suite $(s_n+t_n)$ est hypergéométrique si et seulement si $(t_n)$ et $(s_n)$ sont associées.
\end{proposition}

\begin{demonstration} Posons $a(n)=s_{n+1}/s_n$, $b(n)=t_{n+1}/t_n$, $a(n)=(s_{n+1}+t_{n+1})/(s_n+t_n)$ et
$r(n)=s_n/t_n$. On voit immédiatement que
\[c(n)=\frac{a(n)r(n)+b(n)}{r(n)+1} \mbox{ et } r(n)=\frac{b(n)-c(n)}{c(n)-a(n)}\]
que qui montre que $c(n)$ est rationnel si et seulement si $r(n)$ l'est.
\end{demonstration}

\begin{remarque} Ceci permet d'écrire toute suite qui est somme de suites hypergéométriques comme somme de suites
hypergéométriques deux à deux non associées. Les lemmes qui suivent vont permettre de montrer l'unicité d'une
telle décomposition.
\end{remarque}

\begin{lemme}\label{lemme1} Soit $(t_n^{(1)}),\ldots ,(t_n^{(p)})$ des suites hypergéométriques telles que
\[\forall n,\; t_n^{(1)}+\cdots+t_n^{(p)}=0\]
Alors deux de ces suites sont associées.
\end{lemme}

\begin{demonstration} Par récurrence sur $p$, le résultat étant évident pour $p=2$. Posons
$r_i(n)=t_{n+1}^{(i)}/t_{n}^{(i)}$. On a alors
\[\forall n,\; 0=t_{n+1}^{(1)}+\cdots+t_{n+1}^{(p)}=r_1(n)t_n^{(1)}+\cdots+r_p(n)t_n^{(p)}\]
et comme
\[0=r_p(n)(t_n^{(1)}+\cdots+t_n^{(p)})\]
en soustrayant on obtient
\[(r_1(n)-r_p(n))t_n^{(1)}+\cdots+(r_{p-1}(n)-r_p(n))t_n^{(p-1)}\]
Si pour un $i$, on a $r_i(n)=r_p(n)$, alors le rapport $t_n^{(p)}/t_n^{(i)}$ est constant, et les deux suites
sont associées. Sinon, comme les suites $(r_{i}(n)-r_p(n))t_n^{(i)}$ sont encore hypergéométriques,
l'hypothèse de récurrence assure que deux de ces suites $(r_{i}(n)-r_p(n))t_n^{(i)}$ et
$(r_{j}(n)-r_p(n))t_n^{(j)}$ sont associées, mais il en est alors de même des suites $t_n^{(i)}$ et
$t_n^{(j)}$.
\end{demonstration}

\begin{lemme}\label{lemme2} Soit $(t_n^{(1)}),\ldots ,(t_n^{(p)})$ des suites hypergéométriques telles que
\[\forall n,\; t_n^{(1)}+\cdots+t_n^{(p)}=0\]
Alors pour chaque classe d'équivalence $S$ on a $\sum_{(t_n^{(i)})\in S}t_n^{(i)}=0$.
\end{lemme}

\begin{demonstration} 
Il suffit encore une fois de faire une récurrence sur $p$ et pour cela d'appliquer le lemme \ref{lemme1} en
remplaçant deux suites associées par leur somme (qui est nulle ou bien appartient encore à la même classe
d'équivalence).
\end{demonstration}

\begin{theoreme} \label{theo1}Toute suite qui est somme de suites hypergéométriques s'écrit de manière unique
comme somme de suites hypergéométriques deux à deux non associées.
\end{theoreme}

\begin{demonstration} L'existence d'une telle décomposition découle immédiatement de la proposition \ref{prop1}
comme on l'a déjà remarqué. De plus, si
\[t_n=t_n^{(1)}+\cdots+t_n^{(p)}=u_n^{(1)}+\cdots+u_n^{(q)}\]
les suites $t_n^{(i)}$ étant deux à deux non associées ainsi que les suites $u_n^{(j)}$, on a
\[t_n^{(1)}+\cdots+t_n^{(p)}-u_n^{(1)}-\cdots-u_n^{(q)}=0\]
et le lemme \ref{lemme2} exige que deux des suites, par exemple $t_n^{(1)}$ et $-u_n^{(1)}$ aient une somme
nulle (une classe d'équivalence ne pouvant comporter ni un seul terme ni plus de 2), donc que
$t_n^{(1)}=u_n^{(1)}$. On supprime cette suite commune et on termine l'unicité par une récurrence évidente.
\end{demonstration}







\section{L'algorithme de Gosper}

Donnons nous une série $\sum_n a_n$ hypergéométrique. On appelle
$S_n=\sum_{k=0}^{n}a_k$ la somme partielle d'indice $n$ de la série. L'algorithme de Gosper permet de
détecter le fait que $S_n$ soit une suite hypergéométrique et
d'en déterminer explicitement une expression. C'est donc un algorithme complet dans le sens
où soit il aboutit à une expression explicite de $S_n$ en fonction de $n$, soit il échoue, et on a
dans ce cas une preuve qu'il n'existe pas d'expression hypergéométrique.

En réalité, le fait de démarrer à $k=0$ n'a aucune importance en ce qui concerne le calcul des
sommes partielles de la série (mais il peut en avoir sur la rationalité du
rapport $S_{n+1}/ S_{n}$ comme le montre l'exemple d'une série géométrique) et
nous allons remplacer notre problème initial par celui plus général de
rechercher une suite $(S_n)_{n\in\nmat}$ hypergéométrique telle que $a_n=S_{n+1}-S_{n}$. On aura alors
\[\sum_{k=n_{0}}^n a_k = S_{n+1}-S_{n_{0}}.\]

\begin{proposition} {Le rapport $S_{n+1}/S_{n}$ est une fraction rationnelle en
$n$ si et seulement si il existe des fractions rationnelles $R(X)$ et
$\alpha(X)$ (à coefficients rationnels, réels ou complexes suivant le cas),
telles que \begin{equation}\label{eq1} \forall n\in\nmat\quad {a_{n+1}\over a_{n}}=R(n)\end{equation}
\begin{equation}\label{eq2}\forall n\in\nmat\quad  S_n=\alpha(n) a_n\end{equation}}
\end{proposition}


\begin{demonstration} La condition est bien évidemment suffisante puisque si (\ref{eq1}) et (\ref{eq2}) sont vérifiées, on a
\[{S_{n+1}\over S_{n}}={\alpha(n+1)\over \alpha(n)}\; {a_{n+1}\over
a_{n}}={\alpha(n+1)\over \alpha(n)} R(n).\] La réciproque provient des formules
évidentes
\[{a_{n+1}\over
a_{n}}={S_{n+2}-S_{n+1}\over S_{n+1}-S_{n}}={{S_{n+2}\over S_{n+1}}-1\over
1-{S_{n}\over S_{n+1}}}={\sigma(n+1)-1\over 1-{1\over \sigma(n)}}\]
(en posant $S_{n+1}/S_{n}=\sigma(n)$) et
\[a_n=S_{n+1}-S_{n}=S_n(\sigma(n)-1)\] soit
\[S_n={1\over \sigma(n)-1}a_n.\]
\end{demonstration}

La fraction rationnelle $R$ étant supposée connue, l'algorithme de Gosper va permettre soit de
calculer la fraction rationnelle $\alpha(X)$ quand celle-ci existe, soit d'assurer qu'elle n'existe
pas et qu'il n'existe donc pas de suite $(S_n)$ hypergéométrique telle que $a_n=S_{n+1}-S_n$. 

\begin{theoreme}\label{gosper} Il existe des polynômes $p(X)$, $q(X)$ et $r(X)$ vérifiant les
conditions \begin{equation}\label{eq3}R(X) = {p(X+1) q(X)\over p(X) r(X)}\end{equation}
\begin{equation}\label{eq4}\forall k \in\nmat\quad  q(X)\wedge r(X+k)=1\end{equation}
\begin{equation}\mbox{\label{eq41}$p(X)$ et $q(X)$ sont premiers entre eux}\end{equation}
\begin{equation}\mbox{\label{eq42}$p(X+1)$ et $r(X)$ sont premiers entre eux}\end{equation}
\end{theoreme}

\begin{demonstration} posons $p_0(X)=1$ et $R(X)={q_0(X)\over r_0(X)}$ avec $q_0(X)\wedge r_0(X)=1$. On
définit ensuite par récurrence des polynômes $p_j$, $q_j$ et $r_j$ tels que 
\[R(X) = {p_j(X+1) q_j(X)\over p_j(X) r_j(X)}\] de la manière suivante:

\begin{itemize}
\item si pour tout $h\in\nmat$, $q_j(X)$ et $r_j(X+h)$ sont premiers entre eux, on prend $p=p_j$,
$q=q_j$ et $r=r_j$; 
\item sinon, soit $h$ le plus petit entier naturel tel que $q_j(X)$ et $r_j(X+h)$ ne sont pas
premiers entre eux et appelons $g_j(X)$ leur PGCD; on pose
\[q_{j+1}(X)={q_j(X)\over g_j(X)}, r_{j+1}(X)={r_{j}(X)\over g_j(X-h)} \hbox{ et }
p_{j+1}(X)=p_j(X)g_j(X-1)\ldots g_j(X-k)\] si bien que l'on a encore
\[R(X) = {p_{j+1}(X+1) q_{j+1}(X)\over p_{j+1}(X) r_{j+1}(X)}.\]
\end{itemize}

Comme le degré de $q_{j+1}$ est strictement inférieur à celui de $q_j$, la construction ne peut se
poursuivre indéfiniment et on finit par se trouver dans le premier cas, ce qui permet de déterminer
$p$, $q$ et $r$.

Montrons que $p$ $q$ et $r$ repondent à la question à l'aide des lemmes suivants, où nous noterons
$h_1,\ldots ,h_N$ les différents $h$ introduits au cours du deroulement de l'algorithme et
$h_{N+1}=+\infty $:
\end{demonstration}

\begin{lemme}\label{lemmefond} Soit $k\le i, j\le N$, $h<h_{k+1}$. Alors $q_i(X)$ et $r_j(X+h)$ sont
premiers entre eux.
\end{lemme}

\begin{demonstration} Puisque $q_i(X)\mid q_0(X)$ et $r_j(X)$ divise $r_0(X)$, le pgcd de $q_i(X)$
et de $r_j(X+h)$ divise le pgcd de $q_0(X)$ et de $r_0(X+h)$; il suffit donc de montrer le résultat
lorsque $h$ est parmi $h_1,\ldots ,h_k$. Nous allons montrer le résultat par récurrence sur $k$. Si
$k=0$, il n'y a rien à démontrer. Supposons le résultat vrai pour $k-1$. Alors le résultat découle
de l'hypothèse de récurrence si $h$ est l'un des $h_1,\ldots ,h_{k-1}$. Il reste donc à voir que
$q_i(X)$ et $r_j(X+h_k)$ sont premiers entre eux. Mais comme $q_i(X)\mid q_k(X)$ et
$r_j(X+h_k)\mid r_k(X+h_k)$, il suffit de voir que $q_k(X)\wedge r_k(X+h_k)$ sont premiers entre
eux. Mais on a
\[q_k(X)\wedge r_k(X+h_k)=\frac{q_{k-1}(X)}{g_{k-1}(X)}\wedge \frac{r_{k-1}(X+h_k)}{g_{k-1}(X)}=1\]
par définition de $g_{k-1}(X)$.

Pour $i=j=N$, on obtient que $q(X)=q_N(X)$ et $r(X+h)=r_N(X+h)$ sont premiers entre eux pour tout
$h$.
\end{demonstration}

\begin{lemme} $q(X)$ et $p(X)$ sont premiers entre eux.\end{lemme}
\begin{demonstration} Soit $u(X)$ un facteur commun irréductible de $q(X)$ et $p(X)$. Alors $u$ est
un facteur commun de $q_N(X)$ et de l'un des $g_i(X-j)$ pour $1\le i\le N$ et $1\le j\le h_i$. Mais
comme $r_{i}(X+h_i-j)=r_{i+1}(X+h_i-j)g_i(X-j)$, $u$ est un facteur commun de $q_N(X)$ et de
$r_{i}(X+h_i-j)$ avec $h_i-j<h_i$ ce qui contredit le lemme \ref{lemmefond}.
\end{demonstration}

\begin{lemme} $r(X)$ et $p(X+1)$ sont premiers entre eux.\end{lemme}
\begin{demonstration}
Soit $u(X)$ un facteur commun irréductible de $r(X)$ et $p(X+1)$. Alors $u$ est
un facteur commun de $r_N(X)$ et de l'un des $g_i(X-j+1)$ pour $1\le i\le N$ et $1\le j\le h_i$. Mais
comme $q_{i}(X-j+1)=q_{i+1}(X-j+1)g_i(X-j+1)$, $u$ est un facteur commun de $r_N(X)$ et de
$q_{i}(X-j+1)$ avec $j-1<h_i$ ce qui contredit le lemme \ref{lemmefond}.
\end{demonstration}


\begin{remarque}la construction précedente présente une difficulté du point de vue algorithmique, à
savoir le test de l'existence d'un $k\in\nmat$ tel que $q_j(X)$ et $r_j(X+k)$ ne soient pas premiers
entre eux. On peut envisager d'effectuer ce test de deux manières différentes. La première est
d'introduire le résultant par rapport à la variable $X$ des deux polynômes $q_j(X)$ et
$r_j(X+Y)$ et de rechercher si ce polynôme en $Y$ peut avoir des racines dans $\nmat$ ce qui ne
présente pas de difficulté. La deuxième est, dans le cas où tous les polynômes sont à coefficients
rationnels, d'effectuer la décomposition en polynômes irréductibles normalisés des polynômes $q_j$ et
$r_j$ (cela est possible de manière algorithmique):
\[q_j(X)=\lambda Q_1(X)\ldots Q_m(X),\quad r_j(X)=\mu R_1(X)\ldots R_n(X).\]
Il suffit alors de tester si on peut avoir pour un certain $k\in\nmat$, $Q_s(X)=R_t(X+k)$ pour
un $s\in[1,m]$ et un $t\in[1,n]$. Cela nécessite que les degrés de $Q_s$ et $R_t$
soient les mêmes et la valeur de $k$ s'obtient sans difficulté en considérant le
terme sous dominant de $Q_s(X)-R_t(X+k)$.
\end{remarque}

Voici une implémentation en Maple de la méthode avec l'utilisation du résultant:

\begin{verbatim}
>gosp:=proc(R,n)
>       local Res,S,N,s,p,q,r,h,i,j;
>       q:=numer(R); r:=denom(R); p:=1;
>       Res:=resultant(q,subs(n=n+h,r),n);
>       sol:=[isolve(Res)]; # solutions entières sous forme Maple
>       S:=[seq(subs(sol[i],h),i=1..nops(sol))]; # liste des solutions entières
>       S:=select(x->x>0,S); # on ne garde que les positives
>       N:=nops(S);
>       for i from 1 to N do
>          h:=S[i];  # q(n) et r(n+h) ne sont pas premiers entre eux
>          s:=gcd(q,subs(n=n+h,r)); # pgcd de q(n) et r(n+h)
>          q:=quo(q,s,n);
>          r:=quo(r,subs(n=n-h,s),n);
>          p:=p*product(subs(n=n-j,s),j=1..h) # met a jour p(n), q(n), r(n)
>       od;
>       p,q,r,q*subs(n=n+1,p)/(p*r) # le dernier pour vérification
>    end:
\end{verbatim}

\begin{proposition} Si la fraction rationnelle $\alpha(X)$ existe, alors
elle est de la forme \[\alpha(X)={q(X)\over p(X)} f(X)\]
pour un certain polynôme $f(X)$ vérifiant l'équation fonctionnelle
\begin{equation}\label{eq5}p(X)=q(X+1)f(X+1)-f(X)r(X)\end{equation}
\end{proposition}

\begin{demonstration}On écrit
\[1={S_{n+1}-S_{n}\over a_n}={\alpha(n+1)a_{n+1}-\alpha(n)a_{n}\over a_n}={\alpha(n+1)
R(n)}-\alpha (n)={\alpha(n+1)p(n+1)q(n)\over p(n)r(n)}-\alpha (n)\]
et donc
\[p(n)r(n)=\alpha(n+1)p(n+1)q(n)-\alpha(n)p(n)r(n).\]
Comme cette identité est vérifiée par une infinité de $n$, on a donc
\[p(X)r(X)=\alpha (X+1)p(X+1)q(X)-\alpha (X)p(X)r(X)\]
soit
\begin{equation}\label{eq6}p(X)q(X)=\beta(X+1)q(X)-\beta(X)r(X)\end{equation}
en posant $\beta(X)=\alpha(X)p(X)$.

Supposons que $\beta$ n'est pas un polynôme et écrivons $\beta (X)=\frac{f(X)}{g(X)}$ avec $f$ et $g$ premiers
entre eux et $g$ non constant. Soit $N\geq 0$ maximal tel que $g (X)$ et $g (X+N)$ ne soient pas premiers entre
eux. Soit $u(X)$ un polynôme irréductible divisant à la fois $g (X)$ et $g (X+N)$. Réécrivons l'identité (\ref{eq6})
sous la forme
\begin{equation}\label{eq61}p(X)q(X)g(X)g(X+1)=f(X+1)g(X)q(X)-f(X)g(X+1)r(X)\end{equation}
Puisque $u(X-N)$ divise $g(X)$, il divise  $f(X)g(X+1)r(X)$ d'après (\ref{eq61}); mais comme il ne divise pas
$g(X+1)$ (sinon $u(X)$ diviserait $g(X+N+1)$ ce qui n'est pas) et qu'il ne divise pas $f(X)$ (qui est premier à
$g(X)$), il divise $r(X)$ et donc $u(X+1)$ divise $r(X+N+1)$. De la même façon, $u(X+1)$ divise $g(X+1)$ donc divise
$f(X+1)g(X)q(X)$ d'après (\ref{eq61}); mais il ne divise pas $f(X+1)$ (qui est premier avec $g(X+1)$ ) et il ne
divise pas $g(X)$ (sinon
$u(X)$ diviserait $g(X-1)$ et $g(X+N)$ et donc $g(X)$ et $g(X+N+1)$ ne seraient pas premiers entre eux), donc il
divise $q(X)$. Mais alors $u(X+1)$ divise à la fois $r(X+N+1)$ et $q(X)$ qui sont supposés premiers entre eux
(comme tous les $r(X+h)$ et $q(X)$); c'est absurde. Donc $\beta $ est un polynôme.


%Supposons que $\beta$ n'est pas un polynôme et soit $z$ un pôle complexe de $\beta$. L'identité
%(\ref{eq6}), compte tenu du fait que $p(X)q(X)$ est un polynôme, nous montre que soit $z$ est un pôle de
%$\beta(X-1)$ (ce qui signifie que $z-1$ est un pôle de $\beta$), soit $q(z)=0$. De même, en
%écrivant l'identité (\ref{eq6}) sous la forme
%\[p(X+1)q(X+1)=\beta(X+1)q(X+1)-\beta(X)r(X+1)\]
%on voit que soit $z$ est un pôle de $\beta(X+1)$ (et donc $z+1$ est un pôle de $\beta$), soit
%$r(z+1)=0$. Comme $\beta$ n'a qu'un nombre fini de pôles complexes, choisissons  un pôle $z$ de
%$\beta$ tel que $z-1$ ne soit pas un pôle de $\beta$. On a donc $q(z)=0$ et comme par hypothèse
%$q(X)$ est premier avec tous les $r(X+k)$, on a $\forall k \in\nmat \quad r(z+k)\ne 0$. On en
%déduit que $z+1$ est pôle de $\beta$, puis par récurrence que, pour tout $k$ dans $\nmat$, $z+k$
%est un pôle de $\beta$, ce qui est absurde. Donc $\beta$ est un polynôme.
%
On peut alors réécrire (\ref{eq6}) sous la forme
\[(p(X)-\beta(X+1))q(X)=\beta(X)r(X)\]
et comme $q(X)$ et $r(X)$ sont premiers entre eux, $q(X)$ divise $\beta(X)$, soit
$\beta(X)=q(X)f(X)$ pour un certain polynôme $f(X)$. On reporte alors dans (\ref{eq6}) et on obtient en
simplifiant par $q(X)$, \[p(X)=q(X+1)f(X+1)-f(X)r(X).\]
\end{demonstration}

La proposition précédente ramène donc le problème de l'existence et du calcul de $\alpha(X)$ à
celui de l'existence et du calcul d'un polynôme $f(X)$ vérifiant (\ref{eq5}). Or il est clair que, si l'on
connaît une majoration du degré de $f(X)$, l'identité (\ref{eq5}) conduit à un système d'équations
linéaires en les coefficients de $f(X)$, système dont l'existence et le calcul des solutions se
résolvent sans difficulté. Il suffit donc maintenant de trouver une majoration de ce degré. Pour
cela nous allons transformer l'identité (\ref{eq5}) en l'identité
\begin{equation}p(X)=(q(X+1)-r(X)){f(X+1)+f(X)\over2}+(q(X+1)+r(X)){f(X+1)-f(X)\over 2}\end{equation}

Posons donc $s_{+}(X)=q(X+1)+r(X)$ et $s_{-}(X)=q(X+1)-r(X)$.

\begin{proposition} Si $\deg s_{-}(X)\ne \deg s_{+}(X)-1$ alors
\[\deg f(X) =\deg p(X) - \max(\deg s_{-}(X),\deg s_{+}(X)-1).\]
Si $\deg s_{-}(X)=\deg s_{+}(X)-1=\ell$ et si on a $s_{-}(X)=u_{\ell}X^{\ell}+\ldots$,
$s_{+}(X)=v_{\ell+1}X^{\ell+1}+\ldots$, $n_0=-2 {u_\ell\over v_{\ell+1}}$, alors
\[\deg f \le\begin{cases}\deg p-\ell& \text{si $n_0\not\in\nmat$}\\ \max(\deg p-\ell,n_0)& \text{si $n_0\in\nmat$}\end{cases}\]
\end{proposition}

\begin{demonstration} Appelons $d=\deg f$. Alors $\deg {f(X+1)+f(X)\over2}=d$ et $\deg
{f(X+1)-f(X)\over2}=d-1$. On a donc
\[\deg((q(X+1)-r(X)){f(X+1)+f(X)\over2})=d+\deg s_{-}\] et \[\deg((q(X+1)+r(X)){f(X+1)-f(X)\over
2})=d+\deg s_{+}-1.\] Si $\deg s_{-}(X)\ne \deg s_{+}(X)-1$ alors on a
\[\deg(s_{-}(X){f(X+1)+f(X)\over2}+s_{+}(X){f(X+1)-f(X)\over 2}) = d + \max(\deg
s_{-}(X),\deg s_{+}(X)-1)\] ce qui montre le résultat dans le premier cas.
Dans le deuxième cas, on remarque que si $f(X)=w_dX^d+\ldots$, alors
\[s_{-}(X) {f(X+1)+f(X)\over2} + s_{+}(X) {f(X+1)-f(X)\over 2} = (u_\ell +{1\over
2}v_{\ell+1}d)w_dX^{d+\ell}+\ldots.\]
On a donc soit $d=n_0$, soit $d+\ell=\deg p(X)$ ce qui démontre le deuxième cas.
\end{demonstration}

La suite des opérations est donc claire. Si les majorations obtenues pour $\deg f$ conduisent à une
impossibilité ($\deg f<0$), c'est que notre problème n'a pas de solution. Sinon, il reste à écrire
$f(x)=w_d X^d+\cdots+w_0$, où $d$ majore le degré de $f(X)$ et à reporter dans (\ref{eq5}). Si le système
linéaires aux inconnues $w_0,\ldots,w_d$ n'a pas de solution, c'est que notre problème n'en
a pas non plus. Sinon, on explicite une solution, d'où $f(X)$, puis $\alpha(X)$ et donc le calcul
de $S_n$.


\begin{exemple}
Prenons tout d'abord $a_n=n^2 t^n$, si bien que \[{a_n\over a_{n-1}}={n^2\over(n-1)^2}t=R(n).\] La
méthode ci dessus conduit à écrire
\[R(X)={p(X)q(X)\over p(X-1)r(X)}\]
avec $p(X)=(X-1)^2$, $q(X)=t$ et $r(X)=1$ (la condition $q(X)\wedge r(X+k)=1$ étant bien évidemment
vérifiée). On est donc amené à rechercher un polynôme $f(X)$ vérifiant
$p(X)=f(X)q(X+1)-f(X-1)r(X)$, soit ici $(X-1)^2=tf(X)-f(X-1)$. Si $t\ne 1$, $f(X)$ est
nécessairement de degré 2, et par identification on obtient
\[f(X)={1\over (t-1)}X^2-{\frac {2\,t}{(t-1)^2}}X+{\frac {t\left (t+1\right )}{(t-1)^3}}.\]
On a alors
\[S_n={q(n+1)f(n)\over p(n)} a_n=t^{n+1} \left({1\over (t-1)}n^2-{\frac {2\,t}{(t-1)^2}}n+{\frac
{t\left (t+1\right )}{(t-1)^3}}\right).\] Il faudrait évidemment faire un nouveau calcul de
$f(X)$ pour $t=1$ en cherchant cette fois un polynôme de degré 3.\par Ce premier exemple montre mal
les possibilités offertes par l'algorithme de Gosper, puisqu'on aurait pu aboutir au même résultat
plus simplement. Prenons-en un plus complexe avec \[a_n={n^3-2n^2-1\over
n^4+n^2+1}(n-1)!.\] La même méthode conduit à
$p(X)=X^3-2X^2-1$, $q(X)=X^3-4X^2+6X-3$ et $r(X)=X^2+X+1$. On est alors conduit à chercher un
polynôme $f(X)$ de degré 0, et à \[S_n={n!\over n^2+n+1}.\]
\end{exemple}

\begin{remarque} On a vu dans le théorème \ref{theo1} que la décomposition d'une suite en somme de suites
géométriques deux à deux associées était unique. De plus, la proposition \ref{prop0} montre que si $(S_n)$ est
une suite hypergéométrique, alors $S_n$ et $a_n$ appartiennent à la même classe d'équivalence. Ceci montre que
l'algorithme de Gosper fonctionne directement à l'intérieur de chaque classe d'équivalence de suites
hypergéométriques et permet de répondre directement à la question: étant donné une suite $(a_n)$ qui est somme de
suites hypergéométriques, existe-t-il une suite $S_n$ qui est également somme de
suites hypergéométriques telle que $S_n-S_{n-1}=a_n$.
\end{remarque}

\section{L'algorithme de Soeur Celine}

\subsection{Description de l'algorithme}

L'algorithme de Gosper permet donc de calculer explicitement, lorsque c'est possible, des sommes partielles de
séries hypergéométriques du type $\sum_{k=0}^{n}t_k$. En fait, nous nous trouvons souvent en présence d'autres
types d'expressions à calculer. Donnons nous une application $F:\nmat \times \zmat \rightarrow \cmat$,
$(n,k)\mapsto F(n,k)$ telle que $\forall n\in \nmat ,\; \{k\in \zmat \mid F(n,k)\neq0\}$ soit fini. Posons alors
$f(n)=\sum_{k\in \zmat }F(n,k)$, le but étant de trouver une forme explicite de $f(n)$. 

\begin{exemple} Avec les conventions habituelles que $C_n^k=0$ pour $k<0$ ou $k>n$, on peut chercher une formule
explicite pour $f_p(n)=\sum_{k=0}^{n}(C_n^{k})^p$. On sait par exemple que $f_1(n)=2^n$ et que
$f_2(n)=C_{2n}^{n}$.\end{exemple}

Soeur Celine Fasenmyer a été la première à remarquer en 1945 dans sa thèse soutenue à l'université de Chicago,
que de telles suites $(f(n))_{n\in \zmat }$ vérifiaient très souvent des relations de récurrences linéaires du
type $a_d(n)f(n+d)+a_{d-1}(n)f(n+d-1)+\ldots +a_0(n)f(n)=0$, où les fonctions $a_i$ sont polynomiales. De plus sa
méthode permettait (à l'aide de calculs très éprouvants à faire à la main) de déterminer non seulement si une
telle relation existait, mais encore d'un trouver une à coup sûr.

Pour cela nous supposerons que la fonction $F$ (ou si l'on préfère la suite $F(n,k)$) est doublement
hypergéométrique, c'est à dire que les deux expressions $F(n+1,k)/F(n,k)$ et $F(n,k+1)/F(n,k)$ sont des
fractions rationnelles en les variables $n$ et $k$.

La méthode de Soeur Celine consiste à rechercher tout d'abord des récurrences du type
\[\sum_{i=0}^{I}\sum_{j=0}^{J}a_{i,j}(n)F(n-j,k-i)=0\]
puis à sommer ces récurrences suivant $k\in \zmat $ (en remarquant que pour tout $i$, on a $\sum_{k\in
\zmat}F(n,k-i)=f(n)$) pour obtenir
\[\sum_{j=0}^{J}\left( \sum_{i=0}^{I}a_{i,j}(n)\right)f(n-j)=0\]

La méthode pour obtenir de telles récurrences est la suivante: 
\begin{itemize}
\item supposons qu'une telle récurrence existe, les
 $a_{i,j}(n)$ étant considérés comme des indéterminées
\item diviser toute la relation de récurrence par $F(n,k)$ en remarquant que chaque quotient $F(n-j,k-i)/F(n,k)$
est une fraction rationnelle en $n$ et $k$
\item réduire l'expression au même dénominateur, puis en prendre le numérateur qui est un polynôme en $n$ et $k$
\item écrire ce numérateur sous la forme $\sum_{i}A_i(n)k^i$, en l'ordonnant suivant les puissances de $k$
\item écrire le système $A_0(n)=0,\ldots ,A_i(n)=0,\ldots $ qui est un système linéaire homogène en les
$(a_{i,j}(n)$ dont les coefficients sont des polynômes en $n$
\item chercher une solution non triviale de ce système (qui est nécessairement constituée, à un facteur
multiplicatif près, de fractions rationnelles en $n$)
\end{itemize}

Voici un premier exemple de cette méthode traité avec Maple

\begin{verbatim}
> F:=(n,k)->x^k*k*binomial(n,k): ii:=1: jj:=1:
> eq1:=sum(sum(a[i,j]*F(n-j,k-i),i=0..ii),j=0..jj)/F(n,k):
> eq2:=collect(numer(expand(eq1)),k):
> eqs:={seq(coeff(eq2,k,i)=0,i=0..degree(eq2,k))}:
> sol:=solve(eqs,{seq(seq(a[i,j],i=0..1),j=0..1)}):
> recF:=subs(sol,sum(sum(a[i,j]*FF(n-j,k-i),i=0..1),j=0..1))=0;


          a[0, 1] (n - 1) FF(n, k)
recF := - ------------------------ + a[0, 1] FF(n - 1, k)
                     n

     + a[0, 1] x FF(n - 1, k - 1) = 0

> recf:=subs(sol,sum(sum(a[i,j],i=0..1)*f(n-j),j=0..1))=0:
> f(n)=solve(recf,f(n));

                             (1 + x) f(n - 1) n
                      f(n) = ------------------
                                   n - 1

\end{verbatim}

\noindent et un autre plus compliqué

\begin{verbatim}
> F:=(n,k)->binomial(n,k)^2: ii:=2: jj:=2:\par
> eq1:=sum(sum(a[i,j]*F(n-j,k-i),i=0..ii),j=0..jj)/F(n,k):
> eq2:=collect(numer(expand(eq1)),k):
> eqs:={seq(coeff(eq2,k,i)=0,i=0..degree(eq2,k))}:
> sol:=solve(eqs,{seq(seq(a[i,j],i=0..ii),j=0..jj)}):
> recF:=subs(sol,sum(sum(a[i,j]*FF(n-j,k-i),i=0..ii),j=0..jj))=0;

        a[0, 2] n FF(n, k)   a[0, 2] (2 n - 1) FF(n - 1, k)
recF := ------------------ - ------------------------------
              n - 1                      n - 1

       a[0, 2] (2 n - 1) FF(n - 1, k - 1)
     - ---------------------------------- + a[0, 2] FF(n - 2, k)
                     n - 1

     - 2 a[0, 2] FF(n - 2, k - 1) + a[0, 2] FF(n - 2, k - 2) = 0

> recf:=subs(sol,sum(sum(a[i,j],i=0..ii)*f(n-j),j=0..jj))=0:
> f(n)=solve(recf,f(n));

                              (2 n - 1) f(n - 1)
                     f(n) = 2 ------------------
                                      n

\end{verbatim}

Le travail de Soeur Celine ne s'est pas borné à décrire cette méthode, mais a consisté à montrer que dans des bons
cas  de telles relations de récurrence non
triviales devaient nécessairement exister. Dans le paragraphe suivant, nous allons étudier l'un de ces bon cas tout
en donnant des bornes supérieures pour les
\emph{ordres}
$I$ et
$J$ de ces relations.

\subsection{Existence de relations de récurrences}

Nous nous limiterons à un cas particulier essentiel:

\begin{definition} On dit que $F:\nmat \times\zmat\rightarrow \rmat$ est proprement
hypergéométrique s'il existe $P\in \rmat[n,k]$ des entiers naturels $U$ et $V$ et des entiers
relatifs $a_1,\ldots ,a_U$,$b_1,\ldots ,b_U$,$c_1,\ldots ,c_U$,$u_1,\ldots ,u_U$,
$v_1,\ldots ,v_U$,$w_1,\ldots ,w_u$ tels que
\[F(n,k)=P(n,k)\frac{\product_{i=1}^U(a_in+b_ik+w_i)!}{\product_{i=1}^V(u_in+v_ik+w_i)!}\]
\end{definition}

\begin{theoreme} Soit $F$ une fonction proprement hypergéométrique. Alors il existe des entiers $I$
et $J$, des polynômes $a_{i,j}(n)$, $1\le i\le I$, $1\le j\le J$ non tous nuls tels que
\[\forall (k,n)\in \zmat\times\nmat ,\;  \sum_{i=0}^{I}\sum_{j=0}^{J}a_{i,j}(n)F(n-j,k-i)=0\]
Il existe une telle récurrence non triviale avec $J=J^*=\sum_{s}|b_s|+\sum_{s}|v_s|$ et
$I=I^*=1+\deg P+J^*\left(\sum_{s}|a_s|+\sum_{s}|u_s|-1\right)$.
\end{theoreme}

\begin{demonstration} Nous poserons $m(k,x)=\product_{i=1}^{k}(x+i)$ et
$d(k,x)=\product_{i=0}^{k-1}(x-i)$. On a alors immédiatement, si $F(n,k)=(ak+bk+c)!$
\[\frac{F(n-j,k-i)}{F(n,k)}=\begin{cases}1/d(aj+bi,an+bk+c) & \text{si $aj+bi\ge 0$}\\
m(|aj+bi|,an+bk+c) & \text{si $aj+bi<0$}\end{cases}\]
si bien que dans le cas général de la définition, on a 
\[\frac{F(n-j,k-i)}{F(n,k)}={\frac{\nu_{i,j}(n,k)}{\delta _{i,j}(n,k)}}\]
avec
\[\nu_{i,j}(n,k)=P(n-j,k-i)\product_{a_sj+b_si<0}m(|a_sj+b_si|,a_sn+b_sk+c_s)
\product_{u_sj+vb_si\ge 0}d(u_sj+v_si,u_sn+v_sk+c_s)\]
et
\[\delta _{i,j}(n,k)=P(n,k)\product_{a_sj+b_si\ge 0}d(a_sj+b_si,a_sn+b_sk+c_s)
\product_{u_sj+v_si< 0}m(|u_sj+v_si|,u_sn+v_sk+c_s)\]

Remarquons alors que pour chaque $s$, un multiple commun de tous les
$d(a_sj+b_si,a_sn+b_sk+c_s)$ pour $0\le i\leq  I$ et $0\le j\le J$ et $a_sj+b_si\ge 0$  est
\[\bigvee_{i,j\mid a_sj+b_si\ge 0}d(a_si+b_sj,a_sn+b_sk+c_s)=d(a_s^+J+b_s^+I,a_sn+b_sk+c_s)\]
(avec $x^+=\max(x,0)$)
et un multiple commun de tous les
$m(|u_sj+v_si|,u_sn+v_sk+c_s)$ pour $0\le i\leq  I$ et $0\le j\le J$ et $u_sj+v_si< 0$ qui est
\[\bigvee_{i,j\mid u_sj+v_sj< 0}m(|u_sj+v_si|,u_sn+v_sk+w_s)=m(u_s^-J+v_s^-I,u_sn+v_sk+w_s)\]
(avec $x^-=\max(-x,0)$)
si bien qu'en posant
\[\Delta (n,k)=P(n,k)\product_{s}d(a_s^+J+b_s^+I,a_sn+b_sk+c_s)m(u_s^-J+v_s^-I,u_sn+v_sk+w_s)\]
chacun des $\Delta (n,k)/\delta _{i,j}(n,k)$ est un polynôme en $n$ et $k$. Remarquons d'ailleurs
que le degré en $k$ de ce polynôme est une fonction affine de $I$ et $J$, si bien que le degré en
$k$ du polynôme \[Q_{i,j}(n,k)=\Delta (n,k)\frac{F(n-j,k-i)}{F(n,k)}=\nu_{i,j}(n,k){\frac{\Delta(n,k)}{\delta
_{i,j}(n,k)}}\] est encore une fonction affine de $I$ et $J$. Mais il y a $(I+1)(J+1)$ tels polynômes. Pour $I$ et
$J$ assez grands ces polynômes vont donc former une famille liée dans $(\rmat(n))[k]$ et donc il existera des
fractions rationnelles $a_{i,j}(n)$ non toutes nulles, que nous pourrons supposer être des
polynômes en les multipliant par un facteur adéquat, telles que
\[\sum_{i=0}^{I}\sum_{j=0}^{J}a_{i,j}(n)Q_{i,j}(n,k)=0\]
soit encore
\[\forall (k,n)\in \zmat\times\nmat ,\;  \sum_{i=0}^{I}\sum_{j=0}^{J}a_{i,j}(n)F(n-j,k-i)=0\]
Les valeurs de $I^*$ et $J^*$ qui garantissent une telle récurrence non triviale proviennent d'une
évolution soigneuse des degrés en $k$ des $Q_{i,j}(n,k)$.
\end{demonstration}

\section{L'algorithme de Zeilberger}

L'algorithme de Soeur Celine cherchait à construire une relation de récurrence non triviale que l'on peut écrire sous
la forme
\[\forall (k,n)\in \zmat\times\nmat ,\;  \sum_{i=0}^{I}\sum_{j=0}^{J}a_{i,j}(n)F(n+j,k+i)=0\]
L'algorithme de Zeilberger lui va rechercher une relation \emph{télescopique} du type
\[\forall (k,n)\in \zmat\times\nmat ,\;  \sum_{j=0}^{J}a_{j}(n)F(n+j,k)=G(n,k+1)-G(n,k)\]
où $G(n,k)=R(n,k)F(n,k)$, $R$ étant une fraction rationnelle en $n$ et $k$. Dans ce cas, si pour
tout $n\in \nmat $ la suite $(F(n,k))_{k\in \zmat}$ est à support fini, il en est de même de la
suite $(G(n,k))_{k\in \zmat}$ et on a donc $\sum_{k\in \zmat} (G(n,k+1)-G(n,k))=0$ et doncune
sommation pour $k\in\zmat$ de la relation ci-dessus fournit pour la fonction $f(n)=\sum_{k\in
\zmat}F(n,k)$ la relation de récurrence
\[\sum_{j=0}^{J}a_{j}(n)f(n+j)=0\]

\subsection{Existence d'une relation télescopique}

Nous introduirons sur l'ensemble des fonctions de $\nmat \times \zmat$ dans $\rmat$ les deux
opérateurs linéaires $N$ et $K$ définis par
\[(NF)(n,k)=F(n+1,k)\mbox{ et }(KF)(n,k)=F(n,k+1)\]
Remarquons que pour toute suite doublement hypergéométrique $F$, les deux suites $KF$ et $NF$ sont
égales à une fraction rationnelle en $n$ et $k$ multipliée par $F$, si bien que pour tout polynôme $P$ à
trois variables $P(K,N,n)F$ est encore de ce type.

Supposons trouvée une relation de récurrence non triviale \emph{à la soeur Celine} 
\[\sum_{i=0}^{I}\sum_{j=0}^{J}a_{i,j}(n)F(n+j,k+i)=0\]
En désignant par $P(u,v,w)=\sum_{i,j}a_{i,j}(w)u^iv^j$, on dispose donc d'un polynôme à trois
variables tel que $P(K,N,n)F=0$.Effectuons la division euclidienne de $P(K,N,n)$ par le polynôme
unitaire $K-1$. On peut donc écrire $P(K,N,n)=P(1,N,n)-(K-1)Q(K,N,n)$ et la relation $P(K,N,n)F=0$
s'écrit alors
\[P(1,N,n)F=(K-1)G\]
avec $G=Q(K,N,n)F$ qui est de la forme $G(n,k)=R(n,k)F(n,k)$ pour une certaine fraction rationnelle
$R$. Si l'on pose $P(1,N,n)=\sum_{j=0}^{J}a_j(n)N^j$, on a donc
\[\sum_{i=0}^J a_j(n)F(n+j,k)=G(n,k+1)-G(n,k)\]

Encore faut-il que cette relation soit non triviale. Pour cela, prenons parmi les opérateurs non
triviaux
$P(K,N,n)$ qui annulent $F$ un opérateur qui soit de degré minimal en $K$. Supposons que $P(1,N,n)=0$; on a
alors $(K-1)G=0$, soit $G(n,k+1)=G(n,k)$, donc $G$ ne dépend pas de $k$. Comme $G$ est
hypergéométrique à une seule variable elle satisfait à une récurrence d'ordre 1 à coefficients
polynomiaux, et donc il existe un polynôme $H$ de degré 1 en $N$ tel que $H(N,n)G=0$. Mais
$G=Q(K,N,n)F$ et $Q$ a un degré en $K$ égal à celui de $P$ divminé de 1. Donc $H(N,n)Q(K,N,n)F=0$
alors que $\deg_{K}H(N,n)Q(K,N,n)=\deg_K P(K,N,n)-1$. C'est absurde. Donc $P(1,N,n)\ne 0$ ce qui
garantit que la relation est non triviale.

\begin{theoreme} Soit $F:\nmat \times \zmat\rightarrow \rmat$ proprement hypergéométrique. Alors il
existe un entier $J$, des polynômes $a_0(n),\ldots ,a_J(n)$ non tous nuls et une fraction rationnelle
$R(n,k)$ tels qu'en posant $G(n,k)=R(n,k)F(n,k)$ on ait une relation télescopique
\[\forall (k,n)\in \zmat\times\nmat ,\;  \sum_{j=0}^{J}a_{j}(n)F(n+j,k)=G(n,k+1)-G(n,k)\]
\end{theoreme}

\begin{remarque} Bien entendu une telle relation peut exister pour des fonctions hypergéométriques
plus générales.
\end{remarque}

\subsection{L'algorithme de Zeilberger}

L'obtention d'une relation télescopique à partir d'une récurrence \emph{à la soeur Celine} est de
peu d'intérêt. Nous allons voir qu'en fait l'obtention d'une relation télescopique peut être
beaucoup plus rapide que celle d'une récurrence (qui devient impraticable dès que l'ordre de la
récurrence augmente).

Posons donc \[\frac{F(n,k+1)}{F(n,k)}={\frac{r_1(n,k)}{r_2(n,k)}}\] et 
\[\frac{F(n,k)}{F(n-1,k)}=\frac{s_1(n,k)}{s_2(n,k)}\]
et considérons \[t_k(n)=a_0(n)F(n,k)+a_1(n)F(n+1,k)+\ldots +a_J(n)F(n+J,k)\]
les $a_j(n)$ étant des inconnues à déterminer.

On a alors
\[\frac{F(n+j,k)}{F(n,k)}=\product_{i=0}^{j-1}\frac{F(n+j-i,k)}{F(n+j-i-1,k)}=
\product_{i=0}^{j-1}\frac{s_1(n+j-i,k)}{s_2(n+j-i,k)}\]
et donc
\begin{eqnarray*}\frac{t_{k+1}(n)}{t_k(n)}&=&\frac{\sum_{j=0}^{J}a_j(n)
\product_{i=0}^{j-1}\frac{s_1(n+j-i,k+1)}{s_2(n+j-i,k+1)}}{\sum_{j=0}^{J}a_j(n)
\product_{i=0}^{j-1}\frac{s_1(n+j-i,k)}{s_2(n+j-i,k)}}\frac{r_1(n,k)}{r_2(n,k)}\\
&=&\frac{\sum_{j=0}^{J}a_j(n)
\product_{i=0}^{j-1}{s_1(n+j-i,k+1)}\product_{i=j}^{J}{s_2(n+j-i,k)}}{\sum_{j=0}^{J}a_j(n)
\product_{i=0}^{j-1}{s_1(n+j-i,k)}\product_{i=j}^{J}{s_2(n+j-i,k+1)}}
\frac{r_1(n,k)\product_{i=0}^{J}{s_2(n+j-i,k)}}{r_2(n,k)\product_{i=0}^{J}{s_2(n+j-i,k+1)}}
\end{eqnarray*}
Donc
\[\frac{t_{k+1}(n)}{t_k(n)}=\frac{p_0(k+1)}{p_0(k)}\frac{r(k)}{s(k)}\]
avec
\[p_0(k)=\sum_{j=0}^{J}a_j(n)
\product_{i=0}^{j-1}{s_1(n+j-i,k+1)}\product_{i=j}^{J}{s_2(n+j-i,k)}\]
et
\[r(k)=r_1(n,k)\product_{i=0}^{J}{s_2(n+j-i,k)}\]
\[s(k)=r_2(n,k)\product_{i=0}^{J}s_2(n+j-i,k+1)\]
en remarquant que les coefficients inconnus $a_j(n)$ n'apparaissent que dans $p_0$ et ni dans $r$
ni dans $s$.

Maintenant, on peut mettre la fraction $r(k)/s(k)$ sous forme \emph{de Gosper}
\[\frac{r(k)}{s(k)}=\frac{p_1(k+1)}{p_1(k)}\frac{r_1(k)}{s_1(k)}\]
avec $r_1(k)\wedge s_1(k+j)=1$ ce qui conduit à
\[\frac{t_{k+1}(n)}{t_k(n)}=\frac{p(k+1)}{p(k)}\frac{r_1(k)}{s_1(k)}\]
si l'on pose $p(k)=p_0(k)p_1(k)$. 

Il s'agit maintenant d'une forme standard de Gosper, et on sait que l'on pourra mettre $t_k$ sous
la forme $g_{k+1}- g_k$ si et seulement si la récurrence
\begin{equation}\label{eq8}r_1(k)b(k+1)-s_1(k-1)b(k)=p(k)\end{equation}
admet une solution $b(k)$ polynomiale en $k$. Mais le membre de gauche de cette récurrence est
indépendant des coefficients inconnus $a_j$. On appelle donc $b_0,\ldots ,b_d$ les coefficients de
$b$ et la récurrence (\ref{eq8}) conduit à un système linéaire en les $a_j$ et les $b_i$. Si ce
système a une solution (que l'on peut choisir polynomiale en $n$), cela nous fournit les polynômes
$a_j(n)$ et on a d'après l'algorithme de Gosper
\[G(n,k)=g_k=\frac{s_1(k-1)}{p(k)}b(k)t_k(n)\]

Si ce système n'a pas de solution, on augmente $J$ et on recommence. On finit nécessairement par trouver une solution.

\subsection{Mise en oeuvre}

Dans la bibliothèque Maple EKHAD, trois fonctions implémentent l'algorithme de Zeilberger, les fonctions \texttt{ct},
\texttt{zeil} et \texttt{zeillim}.

La première \texttt{ct} se
charge de rechercher une relation de récurrence à un ordre $J$ donné. Sa syntaxe est 
\begin{center}\texttt{ct(SUMMAND,ORDER,k,n,N)}\end{center}
où \texttt{SUMMAND} désigne la suite hypergéométrique $F(n,k)$ à étudier, \texttt{ORDER} est l'ordre $J$ de la récurrence
à rechercher, \texttt{k} et \texttt{n} sont les noms des variables et \texttt{N} est le nom attribué à l'opérateur de
décalage en $n$ ($(NF)(n,k)=F(n+1,k)$). La fonction renvoie d'une part l'opérateur de récurrence
$\sum_{j=0}^{J}a_j(n)N^j$ et d'autre part la fraction rationnelle $R(n,k)$ de telle sorte que si l'on pose
$G(n,k)=R(n,k)F(n,k)$, on ait
\[\sum_{j=0}^{J}a_{j}(n)(N^jF)(n,k)=G(n,k+1)-G(n,k)\]
soit encore
\[\sum_{j=0}^{J}a_{j}(n)F(n+j,k)=G(n,k+1)-G(n,k)\]

Traitons un premier exemple avec $F(n,k)=(C_n^k)^2$ à l'ordre 1

\begin{verbatim}
> F:=binomial(n,k)^2;

                                            2
                         F := binomial(n, k)

> ct(F,1,k,n,N);

                                                       2
                                      (3 n + 3 - 2 k) k
              -4 n - 2 + (n + 1) N, - ------------------
                                                    2
                                         (n - k + 1)

\end{verbatim}

\noindent ce qui signifie que la suite vérifie la relation de récurrence
\[(-4n-2)F(n,k)+(n+1)F(n+1,k)=G(n,k+1)-G(n,k)\]
avec $G(n,k) = 	-{\frac {\left (3\,n+3-2\,k\right ){k}^{2}}{\left (n-k+1\right )^{2}}}(C_n^k)^2$.

Une fonction personnelle \texttt{show\_ct}  dont la syntaxe est
\begin{center}\texttt{show\_ct(SUMMAND,ORDER,k,n,F,G)}\end{center}
(\texttt{F} et \texttt{G} étant les noms attribués aux deux suites hypergéométriques $F$ et $G$) permet une présentation
plus habituelle de la récurrence	

\begin{verbatim}
> F1:=binomial(n,k)^2;

                                            2
                        F1 := binomial(n, k)

> show_ct(F1,1,k,n,F,G);

(-4 n - 2) F(n, k) + (n + 1) F(n + 1, k) = G(n, k + 1) - G(n, k),

                                 2               2
                (3 n + 3 - 2 k) k  binomial(n, k)
    G(n, k) = - ----------------------------------
                                      2
                           (n - k + 1)

\end{verbatim}

Si l'on désire un calcul direct de la relation de récurrence vérifiée par la suite $f(n)=\sum_{k\in \zmat }F(n,k)$, on
dispose de la fonction \texttt{zeil} dont la syntaxe est 

\begin{center}\texttt{zeil(SUMMAND,k,n,N)}\end{center}

\noindent(avec les mêmes notations que pour la fonction \texttt{ct}). Elle dispose de deux paramètres optionnels
\texttt{MAXORDER} et \texttt{parameter\_list}, l'un pour limiter la recherche d'un $J$ qui convienne, l'autre pour
définir une liste de paramètres formels, le tout étant destiné à accélérer la recherche de la relation.

\begin{verbatim}
> F1:=binomial(n,k)^2;

                                            2
                        F1 := binomial(n, k)

> zeil(F1,k,n,N);

                                                       2
                                      (3 n + 3 - 2 k) k
              -4 n - 2 + (n + 1) N, - ------------------
                                                    2
                                         (n - k + 1)

\end{verbatim}

\noindent ce qui signifie que la suite $f(n)=\sum_{k\in \zmat }(C_n^k)^2=\sum_{k=0}^{n} (C_n^k)^2$ vérifie la relation
de récurrence linéaire homogène
\[(-4n-2)f(n)+(n+1)(Nf)(n)=0\]
soit encore
\[(-4n-2)f(n)+(n+1)f(n+1)=0\]
avec le \emph{certificat} \[R(n,k)=-{\frac {\left (3\,n+3-2\,k\right ){k}^{2}}{\left (n-k+1\right )^{2}}}\]
qui constitue en quelque sorte la preuve de la relation de récurrence. On en décuira facilement que $f(n)=C_{2n}^{n}$.

De la même façon, une fonction personnelle \texttt{show\_zeil} peut servir d'interface plus conventionnelle:
\begin{verbatim}
> F1:=binomial(n,k)^2;

                                            2
                        F1 := binomial(n, k)

> show_zeil(F1,k,n,f);

                (-4 n - 2) f(n) + (n + 1) f(n + 1) = 0
\end{verbatim}


Enfin, la fonction \texttt{zeillim} dont la syntaxe est
\begin{center}\texttt{zeillim(SUMMAND,k,n,N,alpha,beta)}\end{center}
construit la relation de récurrence
\[\sum_{j=0}^{n}a_i(n)f_{\alpha ,\beta }(n+j)=G(n,n-\beta +1)-G(n,\alpha )\]
vérifiée par la somme finie $f_{\alpha ,\beta }(n)=\sum_{k=\alpha }^{n-\beta }F(n,k)$ (attention à la signification du
deuxième paramètre). C'est ainsi que pour trouver la récurrence vérifiée par $f(n)=\sum_{k=0}^{n}C_{3n}^{k}$, on posera

\begin{verbatim}
> F1:=binomial(3*n,k);

                        F1 := binomial(3 n, k)

> zeillim(F1,k,n,N,0,0);

               2                                  2
          (63 n  + 93 n + 32 - 30 n k - 22 k + 4 k ) k
-8 + N, - --------------------------------------------,
           (3 n - k + 1) (3 n + 2 - k) (3 n + 3 - k)

                           2
      binomial(3 n, n) (5 n  + 11 n + 4)
    - ----------------------------------
              (n + 1) (2 n + 1)

\end{verbatim}

\noindent ce qui signifie que la suite vérifie la relation de récurrence linéaire
\[-8f(n)+f(n+1)=
-{\frac {C_{3n}^{n}\left (5\,{n}^{2}+11\,n+4\right )}{\left (n+1
\right )\left (2\,n+1\right )}}\]
avec le certificat \[R(n,k)=-{\frac {\left (63\,{n}^{2}+93\,n+32-30\,nk-22\,k+4\,{k}^{2}\right )k}
{\left (3\,n-k+1\right )\left (3\,n+2-k\right )\left (3\,n+3-k\right )
}}\]
(la troisième valeur retournée est donc le second membre de la relation de récurrence linéaire).

Encore une fois, la fonction personnelle \texttt{show\_zeillim} donnera au résultat une forme plus conventionnelle
\begin{verbatim}
> F1:=binomial(3*n,k);

                        F1 := binomial(3 n, k)

> show_zeillim(F1,k,n,f,0,0);

                                                  2
                             binomial(3 n, n) (5 n  + 11 n + 4)
      -8 f(n) + f(n + 1) = - ----------------------------------
                                     (n + 1) (2 n + 1)
\end{verbatim}
d'où l'on déduira la formule \emph{amusante}
\[\sum_{k=0}^{n}C_{3n}^{k}=2^{3n}\left(1-\sum_{k=0}^{n-1}{\frac {C_{3k}^{k}\left (5\,{k}^{2}+11\,k+4\right )}{2^{3k}\left
(k+1
\right )\left (2\,k+1\right )}}\right)\]	

\subsection{De bien belles formules}

Depuis Gauss, les mathématiciens ont trouvé nombre de formules remarquables reliant séries et suites hypergéométriques.
Ces formules se présentent souvent sous la forme $\sum_{k\in \zmat }F(n,k)=\alpha _n$ où $F(n,k)$ est une suite
doublement hypergéométrique et $\alpha _n$ une suite hypergéométrique. Wilf et Zeilberger ont développé une technique
spécifique pour démontrer de telles formules et même pour en trouver de nouvelles.

La première idée qui vient à l'esprit est d'utiliser l'algorithme de Zeilberger pour construire une relation de
récurrence linéaire vérifiée par $f(n)=\sum_{k\in \zmat }F(n,k)$ puis de résoudre cette récurrence linéaire à l'aide de
l'algorithme de Petkovsek que nous verrons dans le paragraphe suivant.

 En fait on peut faire beaucoup mieux puisque l'on
sait quel résultat on doit obtenir. Il suffit de vérifier que la suite $\alpha _n$ vérifie la même relation de
récurrence linéaire avec les mêmes conditions initiales (par exemple $f(0)=\alpha _0,\ldots f(J-1)=\alpha _{J-1}$.

On peut encore améliorer cette méthode en introduisant la suite $F_1(n,k)=F(n,k)/\alpha _n$. Il suffit de montrer que la
suite $f_1(n)=\sum_{k\in \zmat }F_1(n,k)$ est constante égale à 1. Pour cela, on lui applique l'algorithme de Zeilberger
à l'ordre 1 en cherchant à trouver une suite $G_1(n,k)=R(n,k)F_1(n,k)$ telle que
\[F_1(n+1,k)-F_1(n,k)=G_1(n,k+1)-G_1(n,k)\]
En sommant suivant $k$ ces relations, on obtiendra que $f_1(n)=\sum_{k\in \zmat }F_1(n,k)$ est constante et il suffira
de calculer sa valeur pour un $n$ bien choisi.

\begin{remarque} On voit que $F_1$ et $G_1$ jouent des rôles étonnamment symétriques. En sommant la relation
télescopiques suivant $n$ au lieu de $k$, on obtiendra une autre suite constante $g_1(k)=\sum_{n\in \zmat }G_1(n,k)$, et
donc à toute identité classique ou nouvelle sera associée une identité \emph{duale} qui en général est nouvelle.
\end{remarque}

Nous allons voir dans la suite de ce paragraphe quelques identités fameuses sur les séries hypergéométriques. De manière
à simplifier l'exposé, nous avons laissé de côté toutes les questions de convergence de séries et les passages à la
limite nécessaires lorsque les suites ne sont pas à support fini. Le lecteur comblera facilement ces lacunes. Les
conditions de validité des raisonnements sont explicitées dans l'article de Wilf et Zeilberger cité dans la
bibliographie.

\paragraph{L'identité de Gauss}

Elle s'écrit
\[\F{2}{1}{a,b}{c}{1}=\frac{\Gamma (c-a-b)\Gamma (c)}{\Gamma (c-a)\Gamma (c-b)}\]
ou encore
\[\sum _ k{\frac {\left (a+k\right )!\,\left (b+k\right )!}{\left (c+k
\right )!\,\left (k+1\right )!}}={\frac {\left (a-1\right )!\,\left (c
-a-b-1\right )!\,\left (b-1\right )!}{\left (c-
a-1\right )!\,\left (c-b-1\right )!}}
\]
On va donc démontrer successivement avec Maple que le quotient du membre de gauche par le membre de droite ne dépend ni
de $a$, ni de $b$, ni de $c$.

\begin{verbatim}
> f0:=(a+k)!*(b+k)!*(c-a-1)!*(c-b-1)!/((c+k)!*(a-1)!*(c-a-b-1)!*(k+1)!*(b-1)!);

                (a + k)! (b + k)! (c - a - 1)! (c - b - 1)!
      f0 := ----------------------------------------------------
            (c + k)! (a - 1)! (c - a - b - 1)! (k + 1)! (b - 1)!

> show_ct(f0,1,k,a,F,G);

-F(a, k) + F(a + 1, k) = G(a, k + 1) - G(a, k), G(a, k) = (c + k)

    (k + 1) (a + k)! (b + k)! (c - a - 1)! (c - b - 1)!/((-c + a + 1)

    a (c + k)! (a - 1)! (c - a - b - 1)! (k + 1)! (b - 1)!)

> show_zeil(f0,k,a,f);

                         -f(a) + f(a + 1) = 0

\end{verbatim}

Donc l'expression ne dépend pas de $a$, ni d'ailleurs de $b$ par symétrie.
\begin{verbatim}
> show_zeil(f0,k,c,f);

                         f(c) - f(c + 1) = 0
\end{verbatim}
ce qui montre qu'elle ne dépend pas non plus de $c$. Il suffit donc de montrer la formule pour une valeur bien choisie
de $a,b$ et $c$.

\paragraph{L'identité de K\"ummer}

Elle s'écrit
\[\F{2}{1}{1-b-2a,\;-2a}{b}{-1}={\frac {\left (-1\right )^{a}
\left (2\,a\right )!\,\left (b-1\right )!}{a!\,\left (b+a-1\right )!}}\]

Nous introduirons une fonction auxiliaire \texttt{t\_hypergeom} qui renvoie le terme général de la série
hypergéométrique au lieu de la série elle-même:

\begin{verbatim}
>t_hypergeom:=proc(n,d,z,k)
>        local i;
>        product( GAMMA( n[i]+k ) / GAMMA( n[i] ), i=1..nops(n))*z^k 
>       / (product( GAMMA( d[i]+k ) / GAMMA (d[i] ), i=1..nops(d))*k! )
>    end;
\end{verbatim}

On va donc démontrer successivement avec Maple que le quotient du membre de gauche par le membre de droite ne dépend ni
de $a$, ni de $b$.

\begin{verbatim}
> f5:=t_hypergeom([1-b-2*a,-2*a],[b],-1,k)/convert((2*a)!*(b-1)!/(a!*(b+a-1)!),GAMMA);

                                                 k
f5 := GAMMA(1 - b - 2 a + k) GAMMA(-2 a + k) (-1)  GAMMA(a + 1)

    GAMMA(b + a)/(GAMMA(1 - b - 2 a) GAMMA(-2 a) GAMMA(b + k) k!

    GAMMA(2 a + 1))

> show_zeil(f5,k,a,F);

                       -2 F(a) - 2 F(a + 1) = 0

> show_zeil(f5,k,b,F);

                         -F(b) + F(b + 1) = 0	
\end{verbatim}


\paragraph{Identité de Dixon}

Elle s'écrit
\[\sum _ k\left (-1\right )^{k}C_{b+a}^{a+k}C_{a+c}^{c+k}C_{b+c}^{b+k}={\frac {\left (a+b+c\right )!}{a!\,b!\,c!}}\]
Par symétrie, il suffit de montrer que le quotient ne dépend pas de $a$, soit

\begin{verbatim}
	> f1:=(-1)^k*binomial(a+b,a+k)*binomial(a+c,c+k)*binomial(b+c,b+k)/((a+b+c)!/(a!*b!*c!)):

 > show_zeil(f1,k,a,F);

                       2 F(a) - 2 F(a + 1) = 0

\end{verbatim}



\paragraph{L'identité de Van der Monde}

Elle s'écrit
\[\sum_{k}C_a^kC_b^k=C_{a+b}^a\]
et en voici la \emph{démonstration}

\begin{verbatim}
> f4:=binomial(a,k)*binomial(b,k)/binomial(a+b,a):

> show_zeil(f4,k,a,F);

                         F(a) - F(a + 1) = 0
\end{verbatim}

\section{L'algorithme de Petkovsek}

Nous avons vu comment l'algorithme de soeur Celine ou l'algorithme de Zeilberger permettait
d'obtenir des relations de récurrence à coefficients polynomiaux du type
\[\sum_{j=0}^{J}a_j(n)f(n+j)=0\]
pour les sommes "infinies" de séries doublement hyergéométriques $f(n)=\sum_{k\in \zmat}F(n,k)$.
L'algorithme de Petkovsek va se charger de déterminer les solutions hypergéométriques de ce type de
récurrence. Nous procéderons pour cela en deux étapes, d'abord en cherchant les solutions
polynomiales, puis en nous ramenant à cette situation grâce à la forme de Gosper.

\subsection{Solutions polynomiales}

Nous rechercherons ici des solutions polynomiales de récurrences "affines" du type
\[\sum_{j=0}^{J}a_j(n)f(n+j)=c(n)\]
où $c$ est bien évidemment une fonction polynomiale. Si nous connaissons une majoration du degré
d'une solution $f$, par identification la recherche d'une solution polynomiale se ramène à une
simple résolution d'un système linéaire, et c'est donc une telle majoration que nous allons
rechercher.


Comme d'habitude nous définirons l'opérateur de décalage $N$ par $(Nf)(n)=f(n+1)$. Nous
introduirons également l'opérateur de différence $D$ par $D=N-1$, autrement dit
$(Df)(n)=f(n+1)-f(n)$. Si $f$ est un polynôme, on a $\deg Df=\deg f-1$. Posons
$L=\sum_{j=0}^{J}a_j(n)N^j$. On a alors
\[L=\sum_{j=0}^{J}a_j(n)(D+1)^j=\sum_{j=0}^{J}b_j(n)D^{j}\]
avec $b_j(n)=\sum_{i=j}^{J}C_i^ja_i(n)$.

Posons $d(j,x)=x(x-1)\ldots (x-j+1)$ comme précédemment. Soit $f(n)=\sum_{k=0}^{\delta }f_kn^k$ avec
$f_\delta \ne 0$. Comme $D^j(n^k)=d(j,k)n^{k-j}+\ldots$, le coefficient de plus haut degré de
$b_j(n)D^{j}f(n)$ est $\ell(b_j)f_\delta d(j,\delta )$ (où l'on note $\ell(p)$ le coefficient de
plus haut degré d'un polynôme $p$).

Posons $b=\max_{0\le j\le J}(\deg b_j-j)$. On a bien évidemment $\deg Lf\le b+\delta $. Si
$b+\delta <0$, on a $\delta \le -b-1$. Supposons donc $b+\delta \ge 0$. Le coefficient de
$n^{b+\delta }$ dans $Lf(n)$ est 
\[f_\delta \sum_{\deg b_j-j=b}\ell(b_j)d(j,delta)\]
Soit il est non nul, et alors nécessairement $b+\delta =\deg c$, soit il est nul, et alors $\delta
$ est racine du polynôme $\sum_{\deg b_j-j=b}\ell(b_j)d(j,X)$. En tout état de cause on a en
utilisant les notations ci dessus pour $b$ et $b_j$

\begin{theoreme} Soit $a_0,\ldots ,a_J,c$ des fonctions polynomiales. Si $f$ est une solution
polynomiale de la récurrence
\[\sum_{j=0}^{J}a_j(n)f(n+j)=c(n)\]
alors $\deg f \le \delta $ avec
\[\delta =\max(\deg c -b, -b-1,\delta _1)\]
où $\delta _1$ est la plus grande racine entière de l'équation $\sum_{\deg
b_j-j=b}\ell(b_j)d(j,x)=0$.
\end{theoreme}

Ce théorème permet donc de ramener le problème de la recherche de solutions polynomiales d'une
récurrence linéaire à la résolution d'un système d'équations linéaires.

\subsection{Solutions hypergéométriques}

Nous recherchons donc maintenant les solutions hypergéométriques d'une récurrence linéaire homogène
à coefficients polynomiaux
\[\sum_{j=0}^{J}a_j(n)f(n+j)=0\]

Pour cela, posons $R(n)=\frac{f(n+1)}{f(n)}$ et mettons la fraction rationnelle $R$ sous forme de
Gosper
\[R(n)=\lambda \frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}\]
avec $\lambda $ scalaire non nul, $a,b,c$ étant des polynômes unitaires tels que $\forall j\in
\nmat ,\;  a(X)\wedge b(X+j)=1$, $a(X)\wedge c(X)=1$, $b(X)\wedge c(X+1)=1$ (cf le theoreme
\ref{gosper}).

On a alors
\[f(n+j)=f(n)\product_{i=0}^{i-1}R(n+i)=\lambda^j f(n)\frac{c(n+j)}{c(n)}
\product_{i=0}^{j-1}\frac{a(n+i)}{b(n+i)}\]
Réduisons au même dénominateur l'expression $\sum a_j(n) f(n+j)$ et divisons par $f(n)$. On obtient
l'équation
\[\sum_{j=0}^J a_j(n)\lambda ^j c(n+j)\product_{i=0}^{j-1}{a(n+i)}\product_{i=j}^{J}{b(n+i)}=0\]
On constate que $a(n)$ divise tous les termes pour $j\ge 1$; il doit donc diviser le terme
coreespondant à $j=0$ autrement dit $a(X)$ divise $a_0(X)c(X)\product_{i=0}^{J}{b(n+i)}$; mais
comme il est premier avec $c(X)$ et tous les $b(X+j)$, $a(X)$ doit être un diviseur unitaire de
$a_0(X)$, ce qui ne laisse qu'un nombre fini de possibilités.

De la même façon, $b(n+J-1)$ divise tous les termes pour $j\le J-1$; donc il doit diviser le terme
correspondant à $j=J$, autrement dit $b(X+J-1)$ divise $a_J(X)c(n+J)\product_{i=0}^{J-1}{a(X+i)}$.
Mais il est premier avec $c(X+J)$ (car $b(X)$ est premier à $c(X+1)$) et il est premier à chaque
$a(X+i)$ (car $a(X)$ est premier avec $b(X+J-i-1)$), donc il doit diviser $a_J(X)$. En conclusion
$b(X)$ doit être un diviseur unitaire de $a_J(X-J+1)$, ce qui ne laisse qu'un nombre fini de
possibilités.

Prenons donc un tel couple $a(X)$, $b(X)$ (obtenu par décomposition de $a_0(X)$ et de $a_J(X+J-1)$
en polynômes irréductibles. Posons
\[A_j(X)=a_J(X)\product_{i=0}^{j-1}{a(X+i)}\product_{i=j}^{J}{b(X+i)}\]
On doit donc avoir
\[\sum_{j=0}^J \lambda ^jA_j(n)c(n+j)=0\]
Soit $m$ le maximum des degrés des $A_j$ et $\alpha _j$ le coefficient de $X ^m$ dans $A_j(X)$. En
regardant le coefficient de $n^{m+\delta }$ dans $\sum_{j=0}^J \lambda ^jA_j(n)c(n+j)$ (où $\delta $
désigne le degré de $c(X)$), on voit que nécessairement $\sum_{j=0}^{J}\alpha _j\lambda ^j=0$, ce
qui ne laisse qu'un nombre fini de possibilités pour $\lambda $.

Pour un tel choix du triplet $(a(X),b(X),\lambda )$, $c(X)$ doit être une solution polynomiale de
la récurrence linéaire à coefficients polynomiaux
\begin{equation}\label{recpoly}\sum_{j=0}^J \lambda ^jA_j(n)c(n+j)=0\end{equation}
problème que nous avons résolu dans le paragraphe précédent. Soit la récurrence (\ref{recpoly}) n'a
pas de solution polynomiale, et cela garantit que la récurrence $\sum_{j=0}^{J}a_j(n)f(n+j)=0$ n'a
pas de solution hypergéométrique. Soit elle admet une solution polynomiale $c(n)$; on pose alors
$R(n)=\lambda \frac{a(n)}{b(n)}\frac{c(n+1)}{c(n)}$ et $f(n)=f(0)\product_{i=0}^{n-1}R(n+i)$ est
solution hypergéométrique de la récurrence $\sum_{j=0}^{J}a_j(n)f(n+j)=0$.

\section{Conclusion}

Les algorithmes découverts et mis en oeuvre par Soeur Celine Fasenmyer, Gosper, Zeilberger et Petkovsek ouvrent une
nouvelle voie dans l'utilisation des outils de calcul formel en mathématiques. Les méthodes détaillées ci-dessus
ont été depuis étendu du cas discret au cas continu pour former des équations différentielles vérifiées par des
intégrales définies de type hypergéométrique. Nul doute que les nouveaux outils qui sont à notre disposition
permettront de découvrir dans le futur de nouvelles identités hypergéométriques dont la recherche d'une interprétation
profonde peut ouvrir de nouveaux espaces à la recherche mathématique.

\section{Bibliographie}

L'ouvrage de base est

\noindent Petkovsek M., Wilf H.S., Zeilberger D., $A=B$, A K Peters, Ltd, Wellesley 1996 

Les articles fondamentaux sont

\noindent Fasenmyer, Sister Mary Celine, A note on pure recurrence relations, \emph{Amer. Math. Monthly} {\bf 56}
(1949) 14-17

\noindent Gosper, R. W., Decision procedure for indefinite hypergeometric summation, \emph{Proc. Nat. Acad. Sci. USA}
{\bf 75} (1978), 40-42

\noindent Petkovsek, M, Hypergeometric solutions of linear recurrences with polynomial coefficients, \emph{J.
Symbolic Computation}, {\bf 14} (1992), 243-264

\noindent Wilf H.S. ans Zeilberger D., Rational functions certify combinatorial identities, \emph{J. Amer. Math.
Soc.} {\bf 3} (1990), 147-158

\noindent Zeilberger D., The method of creative telescoping, \emph{J.
Symbolic Computation}, {\bf 11} (1991), 195-204

\end{document}
