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

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

Notation: q is an indeterminate (that commutes with everything). In this paper only, [a]! is short for (1 − q) … (1 − q^{a}), and [a]_{k} is short for (1 − q^{a})(1 − q^{a+1}) … (1 − q^{a+k−1}). The ground field is Q(q). The dependence on q is always understood.

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}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}]!}q^{Jk(k−1)/2}z^{k} ,

(qP 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 indeterminates, and J is an integer. We also assume that the factorization in (P roperHypergeometric) is maximal, i.e. P OL(q^{n}, q^{k}) is as large as possible. This entails that the difference between any of the affine-linear expressions at the top and any of those at the bottom, is never a non-negative integer. Also 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)

Proof: Let

\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]!}q^{Jk(k−1)/2}z^{k} ,

1 Aug. 5, 2004. This replaces an earlier version of June 3, 2004 . 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 at math dot rutgers dot 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 at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/.

f(k) = zq^{Jk} ∏_{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

g(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}} .

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

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}+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}} .

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} ,

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} , 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_{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 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 the a′′_{j}, b′′_{j}, c′′_{j}, d′′_{j} arbitrary symbols.