Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory

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

Sharp Upper Bounds for the Almkvist-Zeilberger Algorithm

This section is a discrete-continuous analog of [MZ].

Theorem Let

F (n, x) = P OL(n, x) · H(n, x) ,  (DiscreteContHyperGeometric)

where P OL(n, x) is a polynomial of (n, x), and

H(n, x) = e^{a(x)/b(x)} · (∏_{p=1}^{P} S_{p}(x)^{α_{p}}) · (\frac{s(x)}{t(x)})^{n}  (P ureDiscreteContHyperGeometric)

where a(x), b(x), s(x), t(x) and S_{p}(x) (1 ≤ p ≤ P) are polynomials of x, while the α_{p}’s are commuting indeterminates, Let

L = deg(b) + deg(s) + deg(t) + ∑_{p=1}^{P} deg(S_{p}) + max(deg(a), deg(b)) − 1 ,

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

∑_{i=0}^{L} e_{i}(n)F (n + i, x) = D_{x}G(x, n) .  (GertDoron)

If F (n, ±∞) = 0 (and hence G(n, ±∞) = 0) it follows, by integrating from −∞ to ∞ that

a(n) := ∫_{−∞}^{∞} F (n, x)dx ,

satisfies the linear recurrence equation with polynomial coefficients

∑_{i=0}^{L} e_{i}(n)a(n + i) = 0 .

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]/. First version: Nov. 15, 2004. Supported in part by the NSF.

Proof: Let L, for now, be any positive integer. Let

\overline{H}(n, x) = e^{a(x)/b(x)} · (∏_{p=1}^{P} S_{p}(x)^{α_{p}}) · \frac{s(x)^{n}}{t(x)^{n+L}} .

We have

∑_{i=0}^{L} e_{i}(n)F (x, n + i) = h(x) · \overline{H}(x, n) ,

where

h(x) := ∑_{i=0}^{L} e_{i}(n)P OL(n + i, x)s(x)^{i}t(x)^{n−i} .

Let q(x) and r(x) be the numerator and denominator, respectively, of the logarithmic derivative of \overline{H}(n, x), i.e.

\frac{D_{x}\overline{H}(n, x)}{\overline{H}(n, x)} = \frac{q(x)}{r(x)}

Write

G(n, x) = \overline{H}(n, x) · r(x) · X(x) ,  (Ansatz)

where X(x) is a polynomial to be determined. Now (GertDoron) is equivalent to

(r′(x) + q(x)) · X(x) + r(x)X′(k) = h(x)  (ContGosper)

Let M := deg(h) − max(deg(r′ + q), deg(r) + 1), and write X(x) with undetermined coefficients. Plugging this into (ContGosper), and equating coefficients, results in deg(h) + 1 equations for L + M + 2 unknowns. In order to guarantee a solution, we need

L + M + 2 > deg(h) + 1 ,

in other words

(L + M + 2) − (deg(h) + 2) ≥ 0 ,

in other words,

L ≥ max(deg(r′ + q), deg(r) + 1) .

We leave it to the reader to verify that the expression on the right is

L = deg(b) + deg(s) + deg(t) + ∑_{p=1}^{P} deg(S_{p}) + max(deg(a), deg(b)) − 1 .

REFERENCES