A Sharp Upper Bound for the Order of The Recurrence Outputted by Zeilberger’s Algorithm ^{1}

Mohamud MOHAMMED ^{2} and Doron ZEILBERGER^{3}

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.

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 proper-hypergeometric function F (n, k) can be written as

F (n, k) = P OL(n, k) · H(n, k) ,  (P roperHypergeometric)

where P OL(n, k) is a polynomial in (n, k) and

H(n, k) = \frac{∏_{j=1}^{A}(a_{j}n + a′_{j}k + a′′_{j})! ∏_{j=1}^{B}(b_{j}n − b′_{j}k + b′′_{j})!}{∏_{j=1}^{C}(c_{j}n + c′_{j}k + c′′_{j})! ∏_{j=1}^{D}(d_{j}n − d′_{j}k + d′′_{j})!}z^{k} ,  (P ureHypergeometric)

where the a_{j}, a′_{j} (1 ≤ j ≤ A) , b_{j}, b′_{j} (1 ≤ j ≤ B) , c_{j}, c′_{j} (1 ≤ j ≤ C) , d_{j}, d′_{j} (1 ≤ j ≤ D) are non-negative integers, and z, a′′_{j} (1 ≤ j ≤ A) , b′′_{j} (1 ≤ j ≤ B) , c′′_{j} (1 ≤ j ≤ C) , d′′_{j} (1 ≤ j ≤ D) are commuting indeterminates, or if one wishes, arbitrary complex numbers, and z! is shorthand for Γ(z + 1).

Zeilberger’s algorithm promises an integer L, polynomials a_{0}(n), a_{1}(n), …, a_{L}(n) in n, and a rational function R(n, k) such that G(n, k) := R(n, k)F (n, k) satisfies

∑_{i=0}^{L} a_{i}(n)F (n + i, k) = G(n, k + 1) − G(n, k) .  (Zpair)

By using Sister Celine’s Method (applied to the generic form (P roperHypergeometric)), it was proved by Wilf and Zeilberger [WZ] (see also [PWZ] or [K]) that one can always guarantee

L ≤ ∑_{j=1}^{A} a′_{j} + ∑_{j=1}^{B} b′_{j} + ∑_{j=1}^{C} c′_{j} + ∑_{j=1}^{D} d′_{j} .  (CelineBound)

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

2 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. mohamudm@math.rutgers.edu , http://www.math.rutgers.edu/~mohamudm/.

3 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu , http://www.math.rutgers.edu/~zeilberg/.

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 directly, we will prove

Theorem: Zeilberger’s algorithm is guaranteed to succeed already with

L = max ( ∑_{j=1}^{A} a′_{j} + ∑_{j=1}^{D} d′_{j} , ∑_{j=1}^{B} b′_{j} + ∑_{j=1}^{C} c′_{j} ) .  (ZBound)

You don’t have to go far to prove sharpness. When F (n, k) = \binom{n}{k}, (ZBound) gives L = 1. Since \binom{n}{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 ≤ 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, mathematically it is now superseded by Zeilberger’s algorithm, even theoretically. Of course, this only applies to single-summation. For multiple summation we still need the multi-variable extension of Sister Celine’s Method described in [WZ].

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 EKHAD, and starting with Maple 6, in Koepf’s built-in package sumtools that evolved into SumTools[Hypergeometric] in Maple 8 and above, inputs a proper-hypergeometric F (n, k) of the form given by (P roperHypergeometric) for specific integers a_{j}, a′_{j}, …, d_{j}, d′_{j} (z and a′′_{j}, …, d′′_{j} may be symbolic), and outputs a relation of the form (Zpair) for some L, that is found by trying L = 0, L = 1, …, 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 directly to the generic F (n, k) given by (P roperHypergeometric). So let’s do it!

It is convenient to introduce

\overline{H}(n, k) = \frac{∏_{j=1}^{A}(a_{j}n + a′_{j}k + a′′_{j})! ∏_{j=1}^{B}(b_{j}n − b′_{j}k + b′′_{j})!}{∏_{j=1}^{C}(c_{j}n + c′_{j}k + c′′_{j} + c_{j}L)! ∏_{j=1}^{D}(d_{j}n − d′_{j}k + d′′_{j} + d_{j}L)!}z^{k} .

Recall that the rising factorial, for z arbitrary, and r non-negative integer, is

(z)_{r} := z(z + 1) … (z + r − 1) = ∏_{i=0}^{r−1}(z + i) .  (RisingF actorial)

We have

\frac{H(n + i, k)}{\overline{H}(n, k)} = ∏_{j=1}^{A}(a_{j}n + a′_{j}k + a′′_{j} + 1)_{ia_{j}} ∏_{j=1}^{B}(b_{j}n − b′_{j}k + b′′_{j} + 1)_{ib_{j}}·

∏_{j=1}^{C}(c_{j}n + c′_{j}k + c′′_{j} + ic_{j} + 1)_{(L−i)c_{j}} ∏_{j=1}^{D}(d_{j}n − d′_{j}k + d′′_{j} + id_{j} + 1)_{(L−i)d_{j}} .  (Ratio)

Let L be any non-negative integer, and consider, for indeterminates e_{0}(n), e_{1}(n), …, e_{L}(n),

∑_{i=0}^{L} e_{i}(n)F (n + i, k) ,

which equals

c(k)\overline{H}(n, k) ,

where

c(k) := ∑_{i=0}^{L} e_{i}(n)P OL(n + i, k) · \frac{H(n + i, k)}{\overline{H}(n, k)} .

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) = \frac{\overline{H}(n, k + 1)}{\overline{H}(n, k)} ,

which simplifies to

\frac{z ∏_{j=1}^{A}(a_{j}n + a′_{j}k + a′′_{j} + 1)_{a′_{j}} ∏_{j=1}^{D}(d_{j}n − d′_{j}k + d′′_{j} + d_{j}L − d′_{j} + 1)_{d′_{j}}}{∏_{j=1}^{B}(b_{j}n − b′_{j}k + b′′_{j} − b′_{j} + 1)_{b′_{j}} ∏_{j=1}^{C}(c_{j}n + c′_{j}k + c′′_{j} + c_{j}L + 1)_{c′_{j}}} .

Hence the polynomials a(k), b(k) featuring in Gosper’s algorithm are

a(k) = z ∏_{j=1}^{A}(a_{j}n + a′_{j}k + a′′_{j} + 1)_{a′_{j}} ∏_{j=1}^{D}(d_{j}n − d′_{j}k + d′′_{j} + d_{j}L − d′_{j} + 1)_{d′_{j}} ,

and

b(k) = ∏_{j=1}^{B}(b_{j}n − b′_{j}k + b′′_{j} − b′_{j} + 1)_{b′_{j}} ∏_{j=1}^{C}(c_{j}n + c′_{j}k + c′′_{j} + c_{j}L + 1)_{c′_{j}} .

Strictly speaking, we have to check the condition

gcd(a(k), b(k + h)) = 1 ,

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 polynomial x(k) such that

a(k)x(k + 1) − b(k − 1)x(k) = c(k) .  (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), …, 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 guarantee a non-zero solution, we need

# unknowns − # equations ≥ 1 ,

and this holds when

[(deg(c) − max(deg(a), deg(b)) + 1) + (L + 1)] − [deg(c) + 1] ≥ 1 ,

which is the same as saying that

L ≥ max(deg(a), deg(b)) .

In particular if L = max(deg(a), deg(b)), then there is always a non-zero solution. But

deg(a) = ∑_{j=1}^{A} a′_{j} + ∑_{j=1}^{D} d′_{j} , deg(b) = ∑_{j=1}^{B} b′_{j} + ∑_{j=1}^{C} c′_{j} .

This concluded the proof.

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 generic case, our new bounds are as sharp as can be, as already demonstrated above.

References

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

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

[K] W. Koepf, “Hypergeometric Summation”, Vieweg, 1998.

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

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

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

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

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