By Mohamud Mohammed and Doron Zeilberger
First Version Written: June 3, 2004,
this much Expanded Version Written: Aug. 10, 2004.
Zeilberger's algorithm starts out with ORDER=0 and climbs up until
success is reached. How do we know that it halts? If we can't prove it,
then it is not an algorithm. The first proof of termination relied
on the deep theory of D-modules, pioneered by Joseph Bernstein, and
no a priori upper bound was given, only the fact that there exists a
successful ORDER. Then W and Z found an explicit upper bound, using
Sister Celine's method. But their `explicit' upper bound was very
dull, as countless experimentations with Zeil in EKHAD showed.
In this article, Mohamud Mohammed and I show that the Z-algorithm
is self-sufficient, i.e. it can use itself to find sharp upper bounds
for the ORDER. But, for this meta-application of the Z-algorithm we
still need humans (at least for now, I won't be surprised if soon
this article would be written by computers), since the input
is no longer a specific proper-hypergeometric function,
but rather the generic form.
.pdf
.ps
.tex
[Appeared in J. Symbolic Computation 39(2005) 201-207.]
Important: This article is accompanied by Maple
packages
ZEILBERGER and
qZEILBERGER
that implement the simplified
Zeilberger and q-Zeilberger Algorithms,
described in the article.
Note added Aug. 10, 2004: The new version
also contains the q-case, and the realization that we now
have simplified versions of Zeilberger and q-Zeilberger.
However, the prsent article is (intentionally!) terse and
unmotivated. We recommend that the readers consult the
Original Version
(.pdf), that however only covers the ordinary case.
Doron Zeilberger's List of Papers