  
%sharpZ.tex: `A Sharp Upper Bound for the Order of The Recurrence
%Outputted by Zeilberger's Algorithm'
%%a Plain TeX file by Mohamud Mohammed and Doron Zeilberger (5 pages)
 
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\Tilde{\char126\relax}
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
 0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
 height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6 
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
%end macros
 
\bf
\centerline
{
A Sharp Upper Bound for the Order of The Recurrence
Outputted by Zeilberger's Algorithm
\footnote{$^1$}
{\eightrm  \raggedright
June 3, 2004 . This version has been superseded by a new
vesrion renamed:
Sharp Upper Bounds for the Orders of The Recurrences
Outputted by the Zeilberger and q-Zeilberger Algorithms,
but we still make this original version available for
historical and especially motivational reasons.
Supported in part by the NSF.
}
}
\rm
\bigskip
\centerline{ 
{\it 
Mohamud MOHAMMED}
\footnote{$^2$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
{\eighttt mohamudm@math.rutgers.edu} , 
{\eighttt http://www.math.rutgers.edu/\Tilde mohamudm/.}
}
and
{\it Doron ZEILBERGER}\footnote{$^3$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt zeilberg@math.rutgers.edu} , 
%\hfill \break
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/.}
} 
}

{\bf Abstract:} By directly tracing Zeilberger's algorithm on
a generic Proper-Hypergeometric Term of two variables, we derive
sharp upper bounds on the outputted recurrence, thereby considerably
improving the previous upper bounds derived by Wilf and Zeilberger
using Sister Celine's Method.

{\bf Prerequisites}: We assume that readers are familiar with
Gosper's [G] and Zeilberger's[Z1][Z2] algorithms, as described in [PWZ],
[GKP], or [K].

By using `reflection', or `shadowing', 
(the fact that $(c+k)!$ is equivalent to $(-1)^k/(-c-k-1)!$)
it is easy to see that
every {\it proper-hypergeometric} function $F(n,k)$ can be written
as
$$
F(n,k)=POL(n,k) \cdot H(n,k)  \quad,
\eqno(ProperHypergeometric)
$$
where $POL(n,k)$ is a polynomial in $(n,k)$ and 
$$
H(n,k)=
{
{\prod_{j=1}^{A} (a_j n + a'_j k + a''_j)!
\,\, \prod_{j=1}^{B} (b_j n - b'_j k + b''_j)!}
\over
{\prod_{j=1}^{C} (c_j n + c'_j k + c''_j)!
\,\, \prod_{j=1}^{D} (d_j n - d'_j k + d''_j)!}
}z^k \quad,
\eqno(PureHypergeometric)
$$
where the 
$a_j,a'_j \,\, (1 \leq j \leq A) \,\,$,
$\,\, b_j,b'_j \,\,(1 \leq j \leq B) \,\, $,
$\,\, c_j,c'_j \,\, (1 \leq j \leq C) \,\, $,
$d_j,d'_j \,\, (1 \leq j \leq D)$
are {\it non-negative integers}, and  $z$, 
$a''_j \,\, (1 \leq j \leq A) \,\,$,
$b''_j \,\, (1 \leq j \leq B) \,\,$,
$c''_j \,\, (1 \leq j \leq C) \,\,$,
$d''_j \,\, (1 \leq j \leq D) \,\,$ are {\it commuting indeterminates},
or if one wishes, arbitrary complex numbers, and $z!$ is shorthand for
$\Gamma(z+1)$.


Zeilberger's algorithm promises an integer $L$,
polynomials $a_0(n), a_1(n), \dots, a_L(n)$ in $n$, and
a rational function $R(n,k)$ such that $G(n,k):=R(n,k)F(n,k)$
satisfies
$$
\sum_{i=0}^L a_i(n)F(n+i,k)=G(n,k+1)-G(n,k) \quad.
\eqno(Zpair)
$$
By using Sister Celine's Method (applied to the generic
form $(ProperHypergeometric)$), it was proved by
Wilf and Zeilberger [WZ] (see also [PWZ] or [K]) that
one can always guarantee 
$$
L \leq \sum_{j=1}^{A} a'_j
\, + \, \sum_{j=1}^{B} b'_j 
\, + \, \sum_{j=1}^{C} c'_j \,
\, + \, \sum_{j=1}^{D} d'_j \quad.
\eqno(CelineBound)
$$
But Sister Celine's algorithm outputs a recurrence that does much
more than is needed (it gives a so-called $k$-free recurrence). By tracing
Zeilberger's algorithm {\it directly}, we will prove

{\bf Theorem}: Zeilberger's algorithm is guaranteed to succeed
already with
$$
L =
\max \left ( \,\,
\sum_{j=1}^{A} a'_j \, + \, \sum_{j=1}^{D} d'_j \quad ,  \quad 
\sum_{j=1}^{B} b'_j  \, + \, \sum_{j=1}^{C} c'_j \,\, \right ) \quad.
\eqno(ZBound)
$$

You don't have to go far to prove sharpness. When
$F(n,k)={{n} \choose {k}}$, $(ZBound)$ gives $L=1$.
Since ${{n} \choose {k}}$ is not gosperable w.r.t. $k$
(try it!), we know that $L>0$. Note that even in this trivial
case, $(CelineBound)$ gives the weaker upper bound $L \leq 2$.

The present article signals the coming-of-age of Zeilberger's algorithm,
that its theoretical justification was hitherto dependent on
Sister Celine's Method (or on Joseph N. Bernstein's deep theory of D-modules).
While Sister Celine's Method is still of
great historical significance, {\it mathematically} it is now superseded
by Zeilberger's algorithm, even theoretically.
Of course, this only applies to {\it single-summation}.
For multiple summation we still need the multi-variable
extension of Sister Celine's Method described in [WZ].

{\bf Rejoice, Rejoice! There is Still A Place 
in the World for Human Mathematicians:
Doing the Z-Algorithm for the Generic Case}

Zeilberger's algorithm, as implemented in {\tt EKHAD}, and starting
with Maple 6, in Koepf's built-in package {\tt sumtools} that evolved
into {\tt SumTools[Hypergeometric]} in Maple 8 and above,
inputs a proper-hypergeometric $F(n,k)$ of the form
given by $(ProperHypergeometric)$ for {\it specific} integers
$a_j,a'_j, \dots, d_j, d'_j$ ($z$ and $a''_j, \dots, d''_j$ may
be symbolic), and outputs a relation of the form $(Zpair)$ for
{\it some } $L$, that is found by trying $L=0, L=1, \dots $, until
success is reached. The termination, until now, was guaranteed
by the weak bound $(CelineBound)$. But we humans can do better,
we can apply the Z-algorithm {\it directly} to
the {\it generic} $F(n,k)$ given by $(ProperHypergeometric)$.
So let's do it!

It is convenient to introduce 
$$
\overline{H}(n,k)=
{
{\prod_{j=1}^{A} (a_j n + a'_j k + a''_j)!
\,\, \prod_{j=1}^{B} (b_j n - b'_j k + b''_j)!}
\over
{\prod_{j=1}^{C} (c_j n + c'_j k + c''_j+c_j L)!
\,\, \prod_{j=1}^{D} (d_j n - d'_j k + d''_j+d_jL)!}}z^k \quad.
$$
Recall that the {\it rising factorial},
for $z$ arbitrary, and $r$ non-negative integer, is  
$$
(z)_r:=z(z+1) \dots (z+r-1)=
\prod_{i=0}^{r-1} (z+i) \quad .
\eqno(RisingFactorial)
$$
We have
\vfill\eject
$$
{{H(n+i,k)}\over {\overline{H} (n,k)}}=
\prod_{j=1}^{A} (a_j n +a'_jk+a''_j+1)_{ia_j}
\prod_{j=1}^{B} (b_j n -b'_jk+b''_j+1)_{ib_j} \cdot
$$
$$
\prod_{j=1}^{C} (c_j n +c'_jk+c''_j+ic_j+1)_{(L-i)c_j}
\prod_{j=1}^{D} (d_j n -d'_jk+d''_j+id_j+1)_{(L-i)d_j} \quad .
\eqno(Ratio)
$$

Let $L$ be any non-negative integer, and consider, for
{\it indeterminates} $e_0(n),e_1(n), \dots, e_L(n)$,
$$
\sum_{i=0}^{L} e_i(n) F(n+i,k) \quad ,
$$
which equals
$$
c(k) \overline{H}(n,k) \quad,
$$
where
$$
c(k):=
\sum_{i=0}^{L} e_i(n) POL(n+i,k) \cdot {{H(n+i,k)}\over {\overline{H} (n,k)}}
\quad .
$$
Now, let's try and apply Gosper to
$c(k) \overline{H}(n,k)$. Here $c(k)$ is the `polynomial part' and
$\overline{H}(n,k)$ is the (potentially) `purely-hypergeometric' part.

We will now follow the notation of Chapter 5 of [PWZ],
except that the discrete variable for us is $k$ instead of  $n$.
First form the ratio, doing everything with respect to $k$,
$$
r(k)={{\overline{H}(n,k+1)} \over  {\overline{H}(n,k)} } \quad ,
$$
which simplifies to
$$
{
{z \prod_{j=1}^{A} (a_j n +a'_jk+a''_j+1)_{a'_j}
\prod_{j=1}^{D} (d_j n -d'_jk+d''_j+d_jL-d'_j+1)_{d'_j}}
\over
{ \prod_{j=1}^{B} (b_j n -b'_jk+b''_j-b'_j+1)_{b'_j}
\prod_{j=1}^{C} (c_j n +c'_jk+c''_j+c_jL+1)_{c'_j}}
} \quad .
$$
Hence the polynomials $a(k)$, $b(k)$ featuring in Gosper's algorithm
are
$$
a(k)=
z \prod_{j=1}^{A} (a_j n +a'_jk+a''_j+1)_{a'_j}
\prod_{j=1}^{D} (d_j n -d'_jk+d''_j+d_jL-d'_j+1)_{d'_j} \quad,
$$
and
$$
b(k)=
 \prod_{j=1}^{B} (b_j n -b'_jk+b''_j-b'_j+1)_{b'_j}
\prod_{j=1}^{C} (c_j n +c'_jk+c''_j+c_jL+1)_{c'_j} \quad.
$$
Strictly speaking, we have to check the condition
$$
gcd(a(k),b(k+h))=1 \quad,
$$
for all non-negative integers $h$, but since everything here is
symbolic-generic, this is automatically true.
The next step in Gosper's algorithm is to look for
a {\it polynomial} $x(k)$ such that
$$
a(k)x(k+1)-b(k-1)x(k)=c(k) \quad .
\eqno(Gosper)
$$
Once again, thanks to genericity, there are no 
miraculous cancellations possible in step 3 (sec. 5.4. of [PWZ]),
and the degree of $x(k)$ is $deg(c)-max(deg(a),deg(b))$.
The `unknowns' are the $deg(c)-max(deg(a),deg(b))+1$ coefficients
of $x(k)$ as well as the $L+1$ (as yet undetermined) coefficients
$a_0(n), a_1(n), \dots , a_L(n)$. Comparing 
coefficients of all the powers of $k$ on both
sides of $(Gosper)$, yields $deg(c)+1$ linear homogeneous equations.
In order to {\it guarantee} a non-zero solution, we need
$$
\#\, unknowns - \#\, equations \geq 1 \quad ,
$$
and this holds when
$$
 [ ( deg(c)-max(deg(a),deg(b))+1 ) + (L+1)] - [deg(c) +1] \geq 1 \quad,
$$
which is the same as saying that
$$
L \geq \max(deg(a),deg(b)) \quad.
$$
In particular if $L=max(deg(a),deg(b))$, then there is always a
non-zero solution.
But
$$
deg(a)=\sum_{j=1}^{A} a'_j
\, + \, \sum_{j=1}^{D} d'_j
\quad, \quad
deg(b)=\sum_{j=1}^{B} b'_j
\, + \, \sum_{j=1}^{C} c'_j \quad.
$$
This concluded the proof. \halmos 

Of course, for non-generic cases, where there is extra symmetry,
$L$ may be even lower, and this accounts for all these `closed-form
miracles'. Symmetry can be sometimes introduced via the
amazing Paule-symmetrization[Pa]. But as far as the {\it generic}
case, our new bounds are as sharp as can be, as already demonstrated
above.


{\bf References}

[G] R. W. Gosper, Jr., {\it 
Decision procedures for indefinite hypergeometric summation},
Proc. Natl. Acad. Sci. USA {\bf 75} (1975), 40-42.

[GKP] R. L. Graham, D. E. Knuth, and O. Patashnik, ``Concrete Mathematics'',
second edition, Addison Wesley, 1993.

[K] W. Koepf, ``{\it Hypergeometric Summation}'', Vieweg, 1998.

[Pa] P. Paule, {\it Short and easy  proofs of the
Rogers-Ramanujan identities and of identities of similar
type}, Electronic J. Combinatorics {\bf 1} (1994) \#R10.

[PWZ] M. Petkovsek, H. S. Wilf and D. Zeilberger,
{\it A=B}, AK Peters, Wellesley, (1996).
[available on-line from the authors' websites.]

[WZ] H.S. Wilf and D. Zeilberger,
{\it An algorithmic proof theory for hypergeometric
(ordinary and "q") multisum/integral identities}, Invent. Math. 
{\bf 108}, 575-633 (1992).
[available on-line from the authors' websites.]

[Z1] D. Zeilberger,
{\it  A Fast Algorithm for proving terminating hypergeometric
identities}, Discrete Math {\bf 80}, 207-211, (1990).
[available on-line from the author's website.]

[Z2] D. Zeilberger,
{\it The method of creative telescoping}, J. Symbolic Computation
{\bf 11}, 195-204 (1991).




\end




