By Mohamud Mohammed and Doron Zeilberger

.pdf .ps .tex

[Appeared in J. Symbolic Computation 39(2005) 201-207.]

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.

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