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

Mohamud MOHAMMED ^{1} and Doron ZEILBERGER^{1}

“Er muβ sozusagen die Leiter wegwerfen, nachdem er auf ihr hinaufgestiegen ist” —–L. Wittgenstein (Logisch-philosophische Abhandlung, 6.54)

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.

Notation. For k integer, (z)_{k} := z(z + 1) … (z + k − 1), [a]_{k} := (1 − q^{a})(1 − q^{a+1}) … (1 − q^{a+k−1}), if k ≥ 0 and (z)_{k} := 1/(z + k)_{−k}, [a]_{k} := 1/[a + k]_{−k}, if k < 0. For a Laurent polynomial p(t) of t, deg(p) is the degree, and ldeg(p) is the low-degree, e.g., if p = 4t^{−3} + 2t^{−1} + 4 + 3t + t^{2}, deg(p) = 2, ldeg(p) = −3.

Theorem. Let

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})_{a′_{j}n+a_{j}k} ∏_{j=1}^{B}(b′′_{j})_{b′_{j}n−b_{j}k}}{∏_{j=1}^{C}(c′′_{j})_{c′_{j}n+c_{j}k} ∏_{j=1}^{D}(d′′_{j})_{d′_{j}n−d_{j}k}} z^{k} ,  (P ureHypergeometric)

where the a_{j}, a′_{j}, b_{j}, b′_{j}, c_{j}, c′_{j}, d_{j}, d′_{j} are non-negative integers, and z, a′′_{j}, b′′_{j}, c′′_{j}, d′′_{j} are commuting indeterminates. We also assume that the factorization in (P roperHypergeometric) is maximal, i.e. P OL(n, k) is of the largest possible degree. Let

L = max ( ∑_{j=1}^{A} a_{j} + ∑_{j=1}^{D} d_{j} , ∑_{j=1}^{B} b_{j} + ∑_{j=1}^{C} c_{j} ) .  (ZBound)

There exist polynomials in n, e_{0}(n), …, e_{L}(n), not all zero, and a rational function R(n, k) such that G(n, k) := R(n, k)F (n, k) satisfies

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

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

Rd., Piscataway, NJ 08854-8019, USA.

[mohamudm,zeilberg] at math dot rutgers dot edu , http://www.math.rutgers.edu/~[mohamudm,zeilberg]/.

Aug. 9, 2004. This replaces an earlier version of June 3, 2004. Accompanied by Maple packages ZEILBERGER and qZEILBERGER downloadable from http://www.math.rutgers.edu/~zeilberg/Zeilberger/sharp.html . Supported in part by the NSF.

Furthermore, in general, L cannot be made any smaller, i.e. the inequality Order ≥ L is sharp.

Proof: Let

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

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

and

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

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) .  (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 ,  (Gosper)

where

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

Note that h(k) is a polynomial since

\frac{H(n + i, k)}{\overline{H}(n, k)} =

∏_{j=1}^{A}(a′_{j}n+a_{j}k+a′′_{j})_{ia′_{j}} ∏_{j=1}^{B}(b′_{j}n−b_{j}k+b′′_{j})_{ib′_{j}} ∏_{j=1}^{C}(c′_{j}n+c_{j}k+c′′_{j}+ic′_{j})_{(L−i)c′_{j}} ∏_{j=1}^{D}(d′_{j}n−d_{j}k+d′′_{j}+id′_{j})_{(L−i)d′_{j}} .

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) = ∑_{i=0}^{M} x_{i}(n)k^{i} ,  (Ansatz1)

substituting into (Gosper), and setting all the coefficients to 0, yields deg(h) + 1 homogeneous linear equations for the M + L + 2 unknowns e_{0}(n), …, e_{L}(n), and x_{0}(n), …, x_{M}(n). For such a not-all-zero solution to exist, we need # unknowns − # equations − 1 ≥ 0, i.e. (M + L + 2) − (deg(h) + 1) − 1 ≥ 0, i.e. L ≥ max(deg(f), deg(g)). But

deg(f) = ∑_{j=1}^{A} a_{j} + ∑_{j=1}^{D} d_{j} , deg(g) = ∑_{j=1}^{B} b_{j} + ∑_{j=1}^{C} c_{j} .

This concludes the proof except that we did not rule out the possibility of e_{0}(n), …, e_{L}(n) being all zero (all we are guaranteed, so far, is that it is not possible for all of e_{0}(n), …, e_{L}(n), and x_{0}(n), …, x_{M}(n) to be zero). But if all the e_{i}(n)’s are zeros, then h(k) is zero and (Gosper) becomes

\frac{X(k + 1)}{X(k)} = \frac{g(k − 1)}{f(k)} .

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 fixed non-negative integers, which is not possible because of the maximality hypothesis about P OL(n, k). Note that the maximality hypothesis always holds, automatically, whenever we have the generic situation with z and the a′′_{j}, b′′_{j}, c′′_{j}, d′′_{j} arbitrary (commuting) 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.

q-Theorem. Let

F (n, k) = P OL(q^{n}, q^{k}) · H(n, k) ,  (qP roperHypergeometric)

where P OL(q^{n}, q^{k}) is a Laurent polynomial in (q^{n}, q^{k}), and

H(n, k) = \frac{∏_{j=1}^{A}[a′′_{j}]_{a′_{j}n+a_{j}k} ∏_{j=1}^{B}[b′′_{j}]_{b′_{j}n−b_{j}k}}{∏_{j=1}^{C}[c′′_{j}]_{c′_{j}n+c_{j}k} ∏_{j=1}^{D}[d′′_{j}]_{d′_{j}n−d_{j}k}} q^{Jk(k−1)/2}z^{k} ,  (qP ureHypergeometric)

where the a_{j}, a′_{j}, b_{j}, b′_{j}, c_{j}, c′_{j}, d_{j}, d′_{j} are non-negative integers, and z, a′′_{j}, b′′_{j}, c′′_{j}, d′′_{j} are indeterminates, and J is an integer. We also assume that the factorization in (qP roperHypergeometric) is maximal, i.e. P OL(q^{n}, q^{k}) is as ‘large’ as possible. Let

L = max ( J + ∑_{j=1}^{A} a_{j}^{2} , ∑_{j=1}^{C} c_{j}^{2} ) + max ( −J + ∑_{j=1}^{D} d_{j}^{2} , ∑_{j=1}^{B} b_{j}^{2} ) .  (qZBound)

There exist polynomials in q^{n}, e_{0}(q^{n}), …, e_{L}(q^{n}), 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

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

Furthermore, in general, L, cannot be made any smaller, i.e. the inequality Order ≥ L is sharp.

Proof: Let

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

f(k) = zq^{Jk} ∏_{j=1}^{A}[a′_{j}n + a_{j}k + a′′_{j}]_{a_{j}} ∏_{j=1}^{D}[d′_{j}(n + L) − d_{j}k + d′′_{j} − d_{j}]_{d_{j}} ,

and

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

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) .  (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 ,  (qGosper)

where

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

Note that h(q^{k}) is a Laurent polynomial (in q^{k}) since

\frac{H(n + i, k)}{\overline{H}(n, k)} =

∏_{j=1}^{A}[a′_{j}n+a_{j}k+a′′_{j}]_{ia′_{j}} ∏_{j=1}^{B}[b′_{j}n−b_{j}k+b′′_{j}]_{ib′_{j}} ∏_{j=1}^{C}[c′_{j}n+c_{j}k+c′′_{j}+ic′_{j}]_{(L−i)c′_{j}} ∏_{j=1}^{D}[d′_{j}n−d_{j}k+d′′_{j}+id′_{j}]_{(L−i)d′_{j}} .

Let

M_{1} := −ldeg(h) − max(−ldeg(f), −ldeg(g))  ,  M_{2} := deg(h) − max(deg(f), deg(g)) .

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) = ∑_{i=−M_{1}}^{M_{2}} x_{i}(n)(q^{k})^{i} ,  (qAnsatz1)

substituting into (qGosper), and setting all the coefficients to 0, yields −ldeg(h)+deg(h)+1 homogeneous linear equations for the M_{1}+M_{2}+L+2 unknowns e_{0}(n), …, e_{L}(n), and x_{−M_{1}}(n), …, x_{M_{2}}(n). For such a not-all-zero solution to exist, we need # unknowns − # equations − 1 ≥ 0, i.e. (M_{1} + M_{2}+L+2)−(−ldeg(h)+deg(h)+1)−1 ≥ 0, i.e. L ≥ max(deg(f), deg(g))+max(−ldeg(f), −ldeg(g)). But

deg(f) = J+∑_{j=1}^{A} a_{j}^{2} , −ldeg(f) = −J+∑_{j=1}^{D} d_{j}^{2} , deg(g) = ∑_{j=1}^{C} c_{j}^{2} , −ldeg(g) = ∑_{j=1}^{B} b_{j}^{2} .

This concludes the proof except that we did not rule out the possibility of e_{0}(n), …, e_{L}(n) being all zero (all we are guaranteed, so far, is that it is not possible for all of e_{0}(n), …, e_{L}(n), and x_{−M_{1}}(n), …, 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

\frac{X(k + 1)}{X(k)} = \frac{g(k − 1)}{f(k)} .

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 fixed non-negative integers, which is not possible because of the maximality hypothesis about P OL(q^{n}, q^{k}). Note that the maximality hypothesis always holds, automatically, whenever we have the generic situation with z and the a′′_{j}, b′′_{j}, c′′_{j}, d′′_{j} arbitrary 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 qEKHAD) on it.

Comments

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 sharp for the generic case. However, sometimes a system of linear equations with more equations than unknowns does have a non-trivial solution, and also, sometimes one can find higher-degree polynomial solutions to (Gosper) and (qGosper), so in 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.

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 explicitly, but, of course, were inspired by it. In fact, they were designed by applying the Zeilberger and q-Zeilberger algorithms once and for all, to the 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 must throw away after we climbed it.

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

The simplified Zeilberger and q-Zeilberger algorithms, apply also to specific, non-generic summands. Start by taking L = 0 and try the 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).

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

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.

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

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.

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

[Kor] T. H. Koornwinder, On Zeilberger’s algorithm and its q-analog, J. Comp. Appl. Math. 48 (1993), 91-111.

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

[PR] P. Paule and A. Riese, 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. 14,Amer. Math. Soc., Providence, RI, 1997.

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

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