Wilf–Zeilberger pair

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

${\displaystyle F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k),}$

${\displaystyle \lim _{M\to \pm \infty }G(n,M)=0.}$

Together, these conditions ensure that

${\displaystyle \sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]=0}$

because the function G telescopes:

${\displaystyle {\begin{aligned}\sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]&{}=\lim _{M\to \infty }\sum _{k=-M}^{M}[F(n+1,k)-F(n,k)]\\&{}=\lim _{M\to \infty }\sum _{k=-M}^{M}[G(n,k+1)-G(n,k)]\\&{}=\lim _{M\to \infty }[G(n,M+1)-G(n,-M)]\\&{}=0-0\\&{}=0.\end{aligned}}}$

Therefore,

${\displaystyle \sum _{k=-\infty }^{\infty }F(n+1,k)=\sum _{k=-\infty }^{\infty }F(n,k),}$

that is

${\displaystyle \sum _{k=-\infty }^{\infty }F(n,k)={\text{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

${\displaystyle G(n,k)=R(n,k)F(n,k-1),}$

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

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

${\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}={2n \choose n}.}$

Divide the identity by its right-hand side:

${\displaystyle \sum _{k=0}^{\infty }{\frac {(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}}{2n \choose n}}=1.}$

Use the proof certificate

${\displaystyle R(n,k)={\frac {2k-1}{2n+1}}}$

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

${\displaystyle {\begin{aligned}F(n,k)&={\frac {(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}}{2n \choose n}},\\G(n,k)&=R(n,k)F(n,k-1).\end{aligned}}}$

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.

• 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.

• Almkvist–Zeilberger method, an analog of WZ method for evaluating definite integrals.
• List of mathematical identities

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