Wilf–Zeilberger pair

In mathematics, specifically combinatorics, a Wilf–Zeilberger pair, or WZ pair, is a pair of functions that can be used to certify certain combinatorial identities. WZ pairs are named after Herbert S. Wilf and Doron Zeilberger, and are instrumental in the evaluation of many sums involving binomial coefficients, factorials, and in general any hypergeometric series. A function's WZ counterpart may be used to find an equivalent and much simpler sum. Although finding WZ pairs by hand is impractical in most cases, Gosper's algorithm provides a method to find a function's WZ counterpart, and can be implemented in a symbolic manipulation program.

Definition

edit

Two functions F and G form a WZ pair if and only if the following two conditions hold:

 
 

Together, these conditions ensure that

 

because the function G telescopes:

 

Therefore,

 

that is

 

The constant does not depend on n. Its value can be found by substituting n = n0 for a particular n0.

If F and G form a WZ pair, then they satisfy the relation

 

where   is a rational function of n and k and is called the WZ proof certificate.

Example

edit

A Wilf–Zeilberger pair can be used to verify the identity

 

Divide the identity by its right-hand side:

 

Use the proof certificate

 

to verify that the left-hand side does not depend on n, where

 

Now F and G form a Wilf–Zeilberger pair.

To prove that the constant in the right-hand side of the identity is 1, substitute n = 0, for instance.

References

edit
  • Marko Petkovsek; Herbert Wilf and Doron Zeilberger (1996). A=B. AK Peters. ISBN 1-56881-063-6.
  • Tefera, Akalu (2010), "What Is . . . a Wilf-Zeilberger Pair?" (PDF), AMS Notices, 57 (4): 508–509.

See also

edit
edit