  
%sharpZ.tex: `Sharp Upper Bounds for the Orders of The Recurrences
%Outputted by the Zeilberger and q-Zeilberger Algorithms'
%%a Plain TeX file by Mohamud Mohammed and Doron Zeilberger (xx 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
{
Sharp Upper Bounds for the Orders of The Recurrences
Outputted by the}
\centerline
{ Zeilberger and q-Zeilberger Algorithms
}
\rm
\bigskip
\centerline{ 
{\it 
Mohamud MOHAMMED}
\footnote{$^1$}
{\eightrm  \raggedright
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA. \hfill\break
{\eighttt [mohamudm,zeilberg] at math dot rutgers dot edu} , 
{\eighttt http://www.math.rutgers.edu/\Tilde [mohamudm,zeilberg]/.}
Aug. 9, 2004. This replaces an earlier version of June 3, 2004. 
Accompanied by Maple packages {\eighttt ZEILBERGER} and
{\eighttt qZEILBERGER} downloadable from 
{\eighttt http://www.math.rutgers.edu/\Tilde zeilberg/Zeilberger/sharp.html .}
Supported in part by the NSF.
}
and
{\it Doron ZEILBERGER}{$^1$}
}
\medskip
{\it ``Er mu$\beta$ sozusagen die Leiter wegwerfen,
nachdem er auf ihr hinaufgestiegen ist''}\hfill\break
-----L. Wittgenstein (Logisch-philosophische Abhandlung, 6.54)
\medskip
{\bf Abstract:} We do what the title promises,
and as a bonus we get much simplified versions of these
algorithms, that do not make any explicit mention of Gosper's algorithm.
\bigskip
{\bf Notation.} For $k$ integer,
$(z)_k:=z(z+1) \dots (z+k-1),[a]_k:=(1-q^a)(1-q^{a+1}) \dots (1-q^{a+k-1})$, 
if $k \geq 0$ 
and $(z)_k:=1/(z+k)_{-k}, [a]_k:=1/[a+k]_{-k}$, if $k<0$.
For a {\it Laurent polynomial} $p(t)$ of $t$, $deg(p)$ is the
{\it degree}, and $ldeg(p)$ is the {\it low-degree}, e.g., if
$p=4t^{-3}+2t^{-1}+4+3t+t^2$, $deg(p)=2, ldeg(p)=-3$.

{\bf Theorem.} Let
$$
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)_{a'_j n + a_j k}  
\prod_{j=1}^{B} (b''_j)_{b'_j n - b_j k}  
}
\over
{\prod_{j=1}^{C} (c''_j)_{c'_j n + c_j k}  
 \prod_{j=1}^{D} (d''_j)_{d'_j n - d_j k}  
}}z^k \quad,
\eqno(PureHypergeometric)
$$
where the 
$a_j,a'_j,b_j,b'_j,c_j,c'_j,d_j,d'_j$ 
are {\it non-negative integers}, and  $z$, 
$a''_j, b''_j, c''_j, d''_j$
are {\it commuting indeterminates}.
We also assume that the factorization
in $(ProperHypergeometric)$ is {\it maximal}, i.e. $POL(n,k)$ is
of the largest possible degree. 
Let
$$
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)
$$
There exist polynomials in $n$, $e_0(n), \dots, e_L(n)$,
{\it not all zero}, and a rational function $R(n,k)$ such
that $G(n,k):=R(n,k)F(n,k)$ satisfies
$$
\sum_{i=0}^L e_i(n)F(n+i,k)=G(n,k+1)-G(n,k) \quad.
\eqno(Zpair)
$$
Furthermore, {\it in general}, $L$ cannot be made any smaller,
i.e. the inequality $Order \geq L$ is {\it sharp}.

{\bf Proof}: Let
$$
\overline{H}(n,k)=
{
{\prod_{j=1}^{A} (a''_j)_{a'_j n + a_j k}  
\prod_{j=1}^{B} (b''_j)_{b'_j n - b_j k}  
}
\over
{\prod_{j=1}^{C} (c''_j)_{c'_j (n+L) + c_j k}  
\prod_{j=1}^{D} (d''_j)_{d'_j (n+L) - d_j k}  
}}z^k \quad,
$$
$$
f(k)=
z \prod_{j=1}^{A} (a'_j n +a_jk+a''_j)_{a_j}
\prod_{j=1}^{D} (d'_j (n+L) -d_jk+d''_j-d_j)_{d_j} \quad,
$$
and
$$
g(k)=
 \prod_{j=1}^{B} (b'_j n -b_jk+b''_j-b_j)_{b_j}
\prod_{j=1}^{C} (c'_j (n+L) +c_jk+c''_j)_{c_j} \quad.
$$
Note that $\overline{H}(n,k+1)/\overline{H}(n,k)=f(k)/g(k)$.
Write
$$
G(n,k)=g(k-1) X(k) \overline{H} (n,k) \quad.
\eqno(Ansatz)
$$
Substituting into $(Zpair)$ and dividing both sides by
$\overline{H}(n,k)$, shows that it is equivalent to
$$
f(k)X(k+1)-g(k-1)X(k)-h(k)=0 \quad ,
\eqno(Gosper)
$$
where 
$$
h(k):=
\sum_{i=0}^{L} e_i(n) POL(n+i,k) \cdot {{H(n+i,k)}\over {\overline{H} (n,k)}}
\quad .
$$
Note that $h(k)$ is a {\it polynomial} since
$$
{{H(n+i,k)}\over {\overline{H} (n,k)}}=
$$
$$
\prod_{j=1}^{A} (a'_j n +a_jk+a''_j)_{ia'_j}
\prod_{j=1}^{B} (b'_j n -b_jk+b''_j)_{ib'_j} 
\prod_{j=1}^{C} (c'_j n +c_jk+c''_j+ic'_j)_{(L-i)c'_j}
\prod_{j=1}^{D} (d'_j n -d_jk+d''_j+id'_j)_{(L-i)d'_j} \quad .
$$

We claim that $(Gosper)$ can always be solved (non-trivially)
with $X(k)$ being a polynomial
of degree $M:=deg(h)-max(deg(f),deg(g))$.
Writing
$$
X(k)=\sum_{i=0}^{M} x_i(n) k^i \quad,
\eqno(Ansatz1)
$$
substituting into $(Gosper)$, and 
setting all the coefficients to $0$, yields
$deg(h)+1$ {\it homogeneous} linear equations for the $M+L+2$ unknowns
$e_0(n), \dots, e_L(n)$, and $x_0(n), \dots, x_M(n)$. For
such a {\it not-all-zero} solution to exist, we need
$\#\, unknowns \, - \, \#\, equations \, -1 \, \geq 0 $,
i.e. $(M+L+2)- (deg(h)+1)-1 \geq 0$, i.e.
$L \geq max(deg(f),deg(g))$. But
$$
deg(f)=\sum_{j=1}^{A} a_j
\, + \, \sum_{j=1}^{D} d_j
\quad, \quad
deg(g)=\sum_{j=1}^{B} b_j
\, + \, \sum_{j=1}^{C} c_j \quad.
$$
This concludes the proof {\it except} that we did not rule out
the possibility of $e_0(n), \dots, e_L(n)$ being all zero
(all we are guaranteed, so far, is that it is not possible for 
{\it all} of $e_0(n), \dots, e_L(n)$, 
{\it and} $x_0(n), \dots, x_M(n)$  to be zero).
But if all the $e_i(n)$'s are zeros, then $h(k)$ is zero
and $(Gosper)$ becomes
$$
{{X(k+1)} \over  {X(k)}}=
{{g(k-1)} \over  {f(k)}} \quad .
$$
Since $X(k)$ is a polynomial, it means that the roots
of $f(k)=0$ differ from the roots of $g(k-1)=0$ by {\it fixed}
non-negative integers, which is not possible because of the
maximality hypothesis about $POL(n,k)$. Note that
the maximality hypothesis always holds, automatically, whenever
we have the {\it generic} situation with $z$ and 
the $a''_j ,b''_j, c''_j, d''_j$
arbitrary (commuting) {\it symbols}.

To prove that $(Zbound)$ is sharp, take $F(n,k)=1/((1)_k(1)_{n-k})$
and note that $L$ cannot be $0$, since otherwise it would have
been gosperable with respect to $k$, but it is not, as can be seen
by performing the Gosper algorithm[G] on it.
\halmos



{\bf q-Theorem.} Let
$$
F(n,k)=POL(q^n,q^k) \cdot H(n,k)  \quad,
\eqno(qProperHypergeometric)
$$
where $POL(q^n,q^k)$ is a Laurent polynomial in $(q^n,q^k)$, and 
$$
H(n,k)=
{
{\prod_{j=1}^{A} [a''_j]_{a'_j n + a_j k}  
\prod_{j=1}^{B} [b''_j]_{b'_j n - b_j k}  
}
\over
{\prod_{j=1}^{C} [c''_j]_{c'_j n + c_j k}  
\prod_{j=1}^{D} [d''_j]_{d'_j n - d_j k}  
}}q^{J k(k-1)/2} z^k \quad,
\eqno(qPureHypergeometric)
$$
where the 
$a_j,a'_j,b_j,b'_j, c_j,c'_j, d_j,d'_j$ 
are {\it non-negative integers}, and  $z$, 
$a''_j, b''_j, c''_j ,d''_j$ are
{\it indeterminates}, and $J$ is an integer.
We also assume that the factorization
in $(qProperHypergeometric)$ is {\it maximal}, i.e. $POL(q^n,q^k)$ is
as `large' as possible.
Let
$$
L =
\max \left ( \,\,
J+\sum_{j=1}^{A} {a_j}^2 \, \, , \,  \,
\sum_{j=1}^{C} {c_j}^2  \,\, \right )
+
\max \left ( \,\,
-J + \sum_{j=1}^{D} {d_j}^2 \, \, , \, \,
\sum_{j=1}^{B} {b_j}^2 \,\, \right ) \quad.
\eqno(qZBound)
$$
There exist polynomials in $q^n$, $e_0(q^n), \dots, e_L(q^n)$,
{\it not all zero}, and a rational function $R(q^n,q^k)$ such
that $G(n,k):=R(q^n,q^k)F(n,k)$ satisfies
$$
\sum_{i=0}^L e_i(q^n)F(n+i,k)=G(n,k+1)-G(n,k) \quad.
\eqno(qZpair)
$$
Furthermore, {\it in general}, $L$, cannot be made any smaller,
i.e. the inequality $Order \geq L$ is {\it sharp}.

{\bf Proof}: Let
$$
\overline{H}(n,k)=
{
{\prod_{j=1}^{A} [a''_j]_{a'_j n + a_j k}  
\prod_{j=1}^{B} [b''_j]_{b'_j n - b_j k}  
}
\over
{\prod_{j=1}^{C} [c''_j]_{c'_j (n+L) + c_j k}  
\prod_{j=1}^{D} [d''_j]_{d'_j (n+L) - d_j k}  
}}q^{J k(k-1)/2} z^k  \quad,
$$
$$
f(k)=
z q^{Jk} \prod_{j=1}^{A} [a'_j n +a_jk+a''_j]_{a_j}
\prod_{j=1}^{D} [d'_j (n+L) -d_jk+d''_j-d_j]_{d_j} \quad,
$$
and
$$
g(k)=
 \prod_{j=1}^{B} [b'_j n -b_jk+b''_j-b_j]_{b_j}
\prod_{j=1}^{C} [c'_j (n+L) +c_jk+c''_j]_{c_j} \quad.
$$
Note that $\overline{H}(n,k+1)/\overline{H}(n,k)=f(k)/g(k)$.
Write
$$
G(n,k)=g(k-1) X(k) \overline{H} (n,k) \quad.
\eqno(qAnsatz)
$$
Substituting into $(Zpair)$ and dividing both sides by
$\overline{H}(n,k)$, shows that it is equivalent to
$$
f(k)X(k+1)-g(k-1)X(k)-h(q^k)=0 \quad ,
\eqno(qGosper)
$$
where 
$$
h(q^k):=
\sum_{i=0}^{L} e_i(n) POL(q^{n}q^{i},q^k) 
\cdot {{H(n+i,k)}\over {\overline{H} (n,k)}}
\quad .
$$
Note that $h(q^k)$ is a {\it Laurent polynomial} (in $q^k$) since
$$
{{H(n+i,k)}\over {\overline{H} (n,k)}}=
$$
$$
\prod_{j=1}^{A} [a'_j n +a_j k+a''_j]_{ia'_j}
\prod_{j=1}^{B} [b'_j n -b_j k+b''_j]_{ib'_j} 
\prod_{j=1}^{C} [c'_j n +c_j k+c''_j+ic'_j]_{(L-i)c'_j}
\prod_{j=1}^{D} [d'_j n -d_j k+d''_j+id'_j]_{(L-i)d'_j} \quad .
$$
Let
$$
M_1:=-ldeg(h)-max(-ldeg(f),-ldeg(g)) \quad \quad , \quad \quad
M_2:=deg(h)-max(deg(f),deg(g)) \quad.
$$
We claim that $(qGosper)$ can always be solved (non-trivially)
with $X(k)$ a Laurent polynomial of $q^k$ of low-degree $-M_1$ and
degree $M_2$.
Writing
$$
X(k)=\sum_{i=-M_1}^{M_2} x_i(n) (q^k)^i \quad,
\eqno(qAnsatz1)
$$
substituting into $(qGosper)$, and 
setting all the coefficients to $0$, yields
$-ldeg(h)+deg(h)+1$ {\it homogeneous} linear equations for the
$M_1+M_2+L+2$ unknowns
$e_0(n), \dots, e_L(n)$, and $x_{-M_1}(n), \dots, x_{M_2}(n)$. For
such a {\it not-all-zero} solution to exist, we need
$\#\, unknowns \, - \, \#\, equations \, -1 \, \geq 0 $,
i.e. $(M_1+M_2+L+2)- (-ldeg(h)+deg(h)+1)-1 \geq 0$, i.e.
$L \geq max(deg(f),deg(g))+max(-ldeg(f),-ldeg(g))$. 
But
$$
deg(f)=J+\sum_{j=1}^{A} {a_j}^2 \quad , \quad
-ldeg(f)=-J+ \sum_{j=1}^{D} {d_j}^2 \quad , \quad 
deg(g)= \sum_{j=1}^{C} {c_j}^2 \quad , \quad
-ldeg(g)= \sum_{j=1}^{B} {b_j}^2 \quad.
$$
This concludes the proof {\it except} that we did not rule out the
possibility of $e_0(n), \dots, e_L(n)$ being all zero (all we are
guaranteed, so far, is that it is not possible for {\it all} of
$e_0(n), \dots, e_L(n)$, {\it and} $x_{-M_1}(n), \dots, x_{M_2}(n)$ to be
zero).  But if all the $e_i(n)$'s are zeros, then $h(q^k)$ is zero and
$(qGosper)$ becomes
$$
{{X(k+1)} \over  {X(k)}}=
{{g(k-1)} \over  {f(k)}} \quad .
$$
Since $X(k)$ is a Laurent polynomial in $q^k$, it means that the roots
of $f(k)=0$ differ from the roots of $g(k-1)=0$ by {\it fixed}
non-negative integers, which is not possible because of the
maximality hypothesis about $POL(q^n,q^k)$. Note that
the maximality hypothesis always holds, automatically, whenever
we have the {\it generic} situation with $z$ and
the $a''_j ,b''_j, c''_j, d''_j$ arbitrary {\it symbols}.

To prove that $(qZbound)$ is sharp, take 
$F(n,k)=q^{k(k-1)/2} /([1]_k[1]_{n-k})$,
and note that $L$ cannot be $0$, since otherwise it would have
been q-gosperable with respect to $k$, but it is not, as can be seen
by performing the q-Gosper algorithm ([Kor][PR], or use {\tt qEKHAD}) on it.
\halmos
\bigskip

{\bf Comments}

{\bf 1.} The bounds in $(ZBound)$ and $(qZBound)$ considerably
improve those of [WZ] (Theorems 3.1 and 5.1, see also [PWZ] and [Koe]),
that relied on Sister Celine's Technique,
and, as we proved, are {\it sharp} for the {\it generic} case.
However, sometimes a system of linear equations with more equations
than unknowns {\it does} have a non-trivial solution, 
and also, sometimes one can find higher-degree polynomial solutions
to $(Gosper)$ and $(qGosper)$, so in {\it specific} cases, it is possible
to have recurrences of lower order. This is the case for all the
non-trivial classical hypergeometric (binomial-coefficient) sums 
that admit a closed-form evaluation.

{\bf 2.} The proofs imply new, simplified, versions of
the Zeilberger[Z1][Z2][PS] and
q-Zeilberger[Kor][PR] algorithms.
These new versions do not rely on Gosper's algorithm {\it explicitly},
but, of course, were inspired by it. In fact, they were
designed by applying the Zeilberger and q-Zeilberger algorithms
{\it once and for all}, to the {\it generic} cases.
It so happens, that in this case, a simplified version
of Gosper (and q-Gosper) suffices, and it is so simple that
it can be incorporated implicitly.
So old-Zeilberger (and hence Gosper and q-Gosper)
is the Wittgensteinian ladder that we {\it must}
throw away after we climbed it.

The {\it running-time} complexity of these new versions
are comparable to the old versions, but their
{\it program-length complexity} (in the sense of Chaitin-Kolmogorov)
are considerably smaller

The simplified Zeilberger and q-Zeilberger algorithms,
apply also to {\it specific}, non-generic summands.
Start by
taking $L=0$ and try the {\it ansatzes} $(Ansatz)$ and
$(qAnsatz)$, but with $M$ (for the q-case: $M_1$, $M_2$)) possibly
larger than the ones in the theorem (which are determined
by plugging them into $(Gosper)$ or $(qGosper)$, and equating
the leading coefficient(s), and finding out whether they can
vanish for integral $M$ (or $M_1,M_2$). Then one solves the
resulting set of linear equations.  If there is no non-trivial
solution, then, one increases $L$ by $1$, until success is reached.
The theorems guarantee that eventually we will succeed, at worst,
with the $L$'s given by $(ZBound)$ and $(qZBound)$.

{\bf 3.} These simplified versions are implemented in
the Maple packages {\tt ZEILBERGER} and {\tt qZEILBERGER}
available from
{\bf http://www.math.rutgers.edu/\Tilde zeilberg/Zeilberger/sharp.html},
where one can also find several examples.

{\bf 4.} The present article was intentionally written in
a terse, unmotivated, style, in order to emphasize its
simplicity and self-containedness. Readers who wish to
see more motivation are welcome to look at an earlier version,
that only covers the ordinary case, that is also available from
the above webpage.

{\bf Acknowledgemet.}
We wish to thank the referees for many helpful comments on
an earlier version.

{\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.

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

[Kor] T. H. Koornwinder, {\it On Zeilberger's algorithm and its
q-analog}, J. Comp. Appl. Math. {\bf 48} (1993), 91-111.

[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.

[PR] P. Paule and A. Riese, {\it A Mathematica $q$-analog
of Zeilberger's algorithm based on an algebraically motivated
approach to $q$-hypergeometric telescoping},
in: ``Special Functions, $q$-series and related topics,
179-210, Fields Inst. Comm. {\bf 14},Amer. Math. Soc., Providence,
RI, 1997.

[PS] P. Paule and M. Schorn, {\it A Mathematica version  of
Zeilberger's algorithm for proving binomial coefficients
identities}, J. Symbolic Comput. {\bf 20} (1995), 673-698.

[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



