Sharp Upper Bounds for the Orders of the Recurrences Outputted by the Zeilberger and q-Zeilberger Algorithms

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

Doron Zeilberger's Home Page