TOPICS
Search

Wilf-Zeilberger Pair

A pair of closed form functions (F,G) is said to be a Wilf-Zeilberger pair if

F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k).
(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

sum_(k)t(n,k)=rhs(n)
(2)

for which the addend t(n,k) vanishes for all k outside some finite interval. Now divide by the right-hand side to obtain

sum_(k)F(n,k)=1,
(3)

where

F(n,k)=(t(n,k))/(rhs(n)).
(4)

Now use a rational function R(n,k) provided by Zeilberger's algorithm, define

G(n,k)=R(n,k)F(n,k).
(5)

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

sum_(k)F(n+1,k)=sum_(k)F(n,k).
(6)

Therefore, sum_(k)F(n,k) is independent of n, and so must be a constant. If F is properly normalized, then it will be true that sum_(k)F(0,k)=1.

For example, consider the binomial coefficient identity

sum_(k=0)^n(n; k)=2^n,
(7)

the function R(n,k) returned by Zeilberger's algorithm is

R(n,k)=k/(2(k-n-1)).
(8)

Therefore,

F(n,k)=(n; k)2^(-n)
(9)

and

G(n,k)=R(n,k)F(n,k)
(10)
=k/(2(k-n-1))(n; k)2^(-n)
(11)
=-(kn!2^(-n))/(2(n+1-k)k!(n-k)!)
(12)
=-(n; k-1)2^(-n-1).
(13)

Taking

F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)
(14)

then gives the alleged identity

(n+1; k)2^(-n-1)-(n; k)2^(-n)=-(n; k)2^(-n-1)+(n; k-1)2^(-n-1)?
(15)

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

F(0,k)=(0; k)={1 for k=0; 0 otherwise,
(16)

so sum_(k)F(0,k)=1 (Petkovšek et al. 1996, pp. 25-27).

For any Wilf-Zeilberger pair (F,G),

sum_(n=0)^inftyG(n,0)=sum_(n=1)^infty[F(n,n-1)+G(n-1,n-1)]
(17)

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

sum_(n=0)^inftyG(n,0)=sum_(n=0)^infty[F(s(n+1),n)+sum_(i=0)^(s-1)G(sn+i,n)] -lim_(n->infty)sum_(k=0)^(n-1)F(sn,k)
(18)
sum_(k=0)^inftyF(0,k)=sum_(n=0)^inftyG(n,0)-lim_(k->infty)sum_(n=0)^kG(n,k),
(19)

and

sum_(n=0)^inftyG(n,0)=sum_(n=0)^infty[sum_(j=0)^(t-1)F(s(n+1),tn+j)+sum_(i=0)^(s-1)G(sn+i,tn)]-lim_(n->infty)sum_(k=0)^(n-1)F_(s,t)(n,k),
(20)

where

F_(s,t)(n,k)=sum_(j=0)^(t-1)F(sn,tk+j)
(21)
G_(s,t)(n,k)=sum_(i=0)^(s-1)G(sn+i,tk)
(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).

See also

Apéry's Constant, Convergence Improvement, Gosper's Algorithm, Sister Celine's Method, Zeilberger's Algorithm

Explore with Wolfram|Alpha

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 m-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. "128000026 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.

Referenced on Wolfram|Alpha

Wilf-Zeilberger Pair

Cite this as:

Weisstein, Eric W. "Wilf-Zeilberger Pair." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Wilf-ZeilbergerPair.html

Subject classifications