a WZ-Pair?

Akalu Tefera

One of the most exciting mathematical discoveries in the early 1990’s was the Wilf-Zeilberger(WZ) Algorithm that can be used for proving, evaluating and searching identities involving hypergeometric terms automatically by computer. A discrete function F (n, k) is called hypergeometric if both

\frac{F (n + 1, k)}{F (n, k)} and \frac{F (n, k + 1)}{F (n, k)}

are rational functions of n and k. The Binomial coefficient \binom{n}{k} = n!/(k!(n − k)!), is the simplest (non-trivial) example.

Suppose that you are faced with identities of the form A = B where A is a sum of terms involving hypergeometric terms and B is a conjectured, simpler answer. For example, the trivial binomial theorem

∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k} = (x + y)^{n}, ,

and the (less trivial) Dixon’s identity

∑_{k=−n}^{n}(−1)^{k}\binom{2n}{n + k}^{3} = \frac{3n!}{n!^{3}}, .

You may ask yourself: “Is there a computerized method that would certify the validity of the identity without human intervention?” (for all n, not just for many special cases). Thanks to Herb Wilf and Doron Zeilbrger, the answer is YES!. Furthermore, unlike computerized proof techniques in other areas, the computerized proofs outputted by their method may be directly verified by mere humans. This certification is achieved by producing what is called a WZ-pair.

A WZ-Pair. A WZ-pair, or Wilf-Zeilberger pair, is a pair of discrete functions (F (n, k), G(n, k)) such that

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k).

Suppose that we want to prove an identity of the form

∑_{k} f(n, k) = r(n) , n ≥ n_{0}.

(for some integer n_{0}, usually 0). If r(n) ≠ 0, divide through by r(n) to get

∑_{k} F (n, k) = 1, where F (n, k) = f(n, k)/r(n).

Let S(n) = ∑_{k} F (n, k). To show S(n) = 1 for all n ≥ n_{0}, it suffices to show that

(1) S(n + 1) − S(n) = 0 for all n ≥ n_{0}

and check that S(n_{0}) = 1 (usually a trivial check). A good way to certify (1) would be to display a “nice” function G(n, k) such that

F (n + 1, k) − F (n, k) = G(n, k + 1) − G(n, k),

for then we simply sum over all integers k to find that (under suitable hypotheses) indeed

S(n + 1) − S(n) = 0.

(since the sum on the right side is telescoping.)

Wilf and Zeilberger proved, in general, that if the summand is hypergeometric, and G(n, k) exists (and surprisingly it does in 99.99 percents of the cases where r(n) is “nice”, and whenever it does, it can be easily found by their algorithm, that is based on the so-called Gosper algorithm), G has the form:

G(n, k) = C(n, k) F (n, k).

Here C is rational in both n and k, and is called the WZ proof certificate.

If r(n) is not “nice” then the so-called Zeilberger algorithm guarantees that it is holonomic (a solution of a linear recurrence equation with polynomial coefficients.

Akalu Tefera is Associate Professor of Mathematics at Grand Valley State University. His email address is teferaa@gvsu.edu

The WZ algorithm is implemented in Zeilberger’s Maple package EKHAD available from www.

math.rutgers.edu/~zeilberg/ and the built-

in SumTools package in Maple. A Mathematica package written by Peter Paule and Markus Schorn is also available.

Example. Suppose we want to prove:

∑_{k}(−1)^{k}\binom{n}{k}\binom{2k}{k}4^{n−k} = \binom{2n}{n}.

Applying the WZ algorithm to the summand (−1)^{k}\binom{n}{k}\binom{2k}{k}4^{n−k}, yields a WZ-Pair (F, G), where

F (n, k) = \frac{(−1)^{k}\binom{n}{k}\binom{2k}{k}4^{n−k}}{\binom{2n}{n}} ,

G(n, k) = C(n, k)F (n, k) and

C(n, k) = −\frac{2k^{2}}{(n + 1 − k)(2n + 1)}.

Doubling the fun! Besides getting a very short proof for any given summation identity, one can discover a new identity from a WZ-pair. Here is how. Suppose the identity

∑_{k} F (n, k) = r(n), (n ≥ n_{0})

yields a WZ-pair (F, G). If the WZ-pair satisfies (i) for each k, f_{k} := lim_{n→∞} F (n, k) < ∞ and (ii)

lim_{L→∞} ∑_{n≥n_{0}} G(n, L) = 0, then we get a new iden-

tity

∑_{n≥n_{0}} G(n, k) = ∑_{j≤k−1}(f_{j} − F (n_{0}, j)).

Example. The identity

∑_{k} k\binom{n}{k} = n2^{n−1}, n ≥ 1

has a WZ-pair (F, G), where

F = \frac{k}{2^{n−1}n}\binom{n}{k} and G = −\frac{1}{2^{n}} \binom{n − 1}{k − 2}.

Furthermore, the WZ-pair satisfies the above conditions, and hence we have a new identity

∑_{n=1}^{∞} \frac{1}{2^{n}} \binom{n − 1}{k − 2} = \{ \begin{matrix}1 & if k ≥ 2 \\ 0 & otherwise \end{matrix} .

Finding closed forms for sums. Does the WZ method apply to find directly the B part of A = B? The answer is yes whenever the summands in A are proper-hypergeometric. A discrete function F (n, k) is proper-hypergeometric if it can be written in the form:

P (n, k)\frac{∏_{i=1}^{I}(a_{i}n + b_{i}k + c_{i})!}{∏_{j=1}^{J}(u_{j}n + v_{j}k + w_{j})!}x^{n}y^{k},

where

• P (n, k) is a polynomial in n and k,

• I and J are fixed integers,

• a_{i}, b_{i}, u_{j}, v_{j} are integers, and

• c_{i}, w_{j}, x, y may depend on parameters.

Finding closed forms for sums relies on the fundamental theorem of WZ theory which states that if F (n, k) is a proper-hypergeometric term, then there exists a (proper) hypergeometric term G(n, k) such that

(2) ∑_{j=0}^{J} a_{j}(n)F (n+j, k) = G(n, k +1)−G(n, k),

where a_{j}(n) are polynomials in n. Suppose we want to find a closed form expression for

S(n) = ∑_{k} F (n, k)

where F is a proper-hypergeometric. Then by the fundamental theorem we get a recurrence equation of the form (2) for F (n, k). Summing both sides of (2) with respect to k yields

∑_{j=0}^{J} a_{j}(n)S(n) = 0 .

(assuming, as is usually the case that G(n, ±∞) = 0). If the order of the recurrence, J, happens to be 1, then we can easily solve this recurrence and get the closed-form solution. If J > 1, then Petkovšek algorithm’s can be used to find a closed-form solution, if one exists, or else rule out this possibility. Either way, describing a sequence {S(n)} in terms of the linear recurrence equation with polynomial coefficients that it satisfies, together with the initial conditions (S(0), S(1), …, S(J − 1)) is an effective and canonical way to describe it, and is almost as good as “closed-form”. The recurrence can also be used to compute, in linear time, and constant memory, as many terms as desired.

Proving identities of the form A = B when B has no simple form. Suppose we want to prove identities of the form

∑_{k} F (n, k) = ∑_{k} H(n, k), (n ≥ n_{0}).

Let L(n) and R(n) be the left and right sides of the equation. Find recurrences for each side, and see whether they coincide, and check the initial conditions.

Further Reading [1 ] M. Petkovšek, H. S. Wilf, and D. Zeilberger, A = B, A. K. Peters, Wellesley, Massachusetts, 1996.

[2 ] H. Wilf and D. Zeilberger, Rational function certify combinatorial identities, J. Amer. Math. Soc. 3 (1990), 147-158.