Wilf-Zeilberger Pair

A pair of closed form functions  is said to be a Wilf-Zeilberger pair if

(1)

The Wilf-Zeilberger formalism provides succinct proofs of known identities and allows new identities to be discovered whenever it succeeds in finding a proof certificate for a known identity. However, if the starting point is an unknown hypergeometric sum, then the Wilf-Zeilberger method cannot discover a closed form solution, while Zeilberger's algorithm can.

Wilf-Zeilberger pairs are very useful in proving hypergeometric identities of the form

(2)

for which the addend  vanishes for all  outside some finite interval. Now divide by the right-hand side to obtain

(3)

where

(4)

Now use a rational function  provided by Zeilberger's algorithm, define

(5)

The identity (◇) then results. Summing the relation over all integers then telescopes the right side to 0, giving

(6)

Therefore,  is independent of , and so must be a constant. If  is properly normalized, then it will be true that .

For example, consider the binomial coefficient identity

(7)

the function  returned by Zeilberger's algorithm is

(8)

Therefore,

(9)

and

			(10)
			(11)
			(12)
			(13)

Taking

(14)

then gives the alleged identity

(15)

Expanding and evaluating shows that the identity does actually hold, and it can also be verified that

(16)

so  (Petkovšek et al. 1996, pp. 25-27).

For any Wilf-Zeilberger pair ,

(17)

whenever either side converges (Zeilberger 1993). In addition,

(18)

(19)

and

(20)

where

			(21)
			(22)

(Amdeberhan and Zeilberger 1997). The latter identity has been used to compute Apéry's constant to a large number of decimal places (Wedeniwski).

REFERENCES:

Amdeberhan, T. and Zeilberger, D. "Hypergeometric Series Acceleration via the WZ Method." Electronic J. Combinatorics 4, No. 2, R3, 1-3, 1997. http://www.combinatorics.org/Volume_4/Abstracts/v4i2r3.html. Also available at http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/accel.html.

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. "The Wilf-Zeilberger Algorithm." §3.1 in Experimental Mathematics in Action. Wellesley, MA: A K Peters, pp. 53-55, 2007.

Cipra, B. A. "How the Grinch Stole Mathematics." Science 245, 595, 1989.

Koepf, W. "Algorithms for -fold Hypergeometric Summation." J. Symb. Comput. 20, 399-417, 1995.

Koepf, W. "The Wilf-Zeilberger Method." Ch. 6 in Hypergeometric Summation: An Algorithmic Approach to Summation and Special Function Identities. Braunschweig, Germany: Vieweg, pp. 80-92, 1998.

Petkovšek, M.; Wilf, H. S.; and Zeilberger, D. "The WZ Phenomenon." Ch. 7 in A=B. Wellesley, MA: A K Peters, pp. 121-140, 1996. http://www.cis.upenn.edu/~wilf/AeqB.html.

Wedeniwski, S. " Digits of Zeta(3)." http://pi.lacim.uqam.ca/eng/records_en.html.

Wilf, H. S. and Zeilberger, D. "Rational Functions Certify Combinatorial Identities." J. Amer. Math. Soc. 3, 147-158, 1990.

Zeilberger, D. "The Method of Creative Telescoping." J. Symb. Comput. 11, 195-204, 1991.

Zeilberger, D. "Closed Form (Pun Intended!)." Contemporary Math. 143, 579-607, 1993.