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 sure method to find a function's WZ counterpart, and can be implemented in a  symbolic manipulation program.

Definition

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

: $F(n+1,k)-F(n,k) = G(n,k+1)-G(n,k),$
: $\lim_G(n,M) = 0.$

Together, these conditions ensure that

: \sum_^\infty (n+1,k)-F(n,k)= 0

because the function ''G'' telescopes:

:\begin \sum_^\infty (n+1,k)-F(n,k)
& = \lim_ \sum_^M (n+1,k)-F(n,k)\\
& = \lim_ \sum_^M (n,k+1)-G(n,k)\\
& = \lim_ (n,M+1)-G(n,-M)\\
& = 0-0 \\
& = 0.
\end

Therefore,

: $\sum_^\infty F(n+1,k) = \sum_^\infty F(n,k),$

that is

: $\sum_^\infty F(n,k) = const.$

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

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

: $G(n,k) = R(n,k) F(n,k-1),$

where $R(n,k)$ is a rational function of ''n'' and ''k'' and is called the ''WZ proof certificate''.

Example

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

: $\sum_^\infty (-1)^k 4^ = .$

Divide the identity by its right-hand side:

: $\sum_^\infty \frac = 1.$

Use the proof certificate

: $R(n,k)=\frac$

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

:$\begin F(n,k)&=\frac, \\ G(n,k)&=R(n,k)F(n,k-1). \end$

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

*
* .

See also

* Almkvist–Zeilberger method, an analog of WZ method for evaluating definite integrals.
*

External links

Gosper's algorithm
gives a method for generating WZ pairs when they exist.
Generatingfunctionology
provides details on the WZ method of identity certification.

{{DEFAULTSORT:Wilf-Zeilberger pair
Combinatorics