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)=\mathop{\rm rhs}(n)$$ (2)

for which the Summand $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)\equiv {t(n,k)\over\mathop{\rm rhs}(n)}.$$ (4)

Now use a Rational Function $R(n,k)$ provided by Zeilberger's Algorithm, define

$$G(n,k)\equiv R(n,k)F(n,k).$$ (5)

The identity (1) 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\choose k}=2^n,$$ (7)

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

$$R(n,k)={k\over 2(k-n-1)}.$$ (8)

Therefore,

$$F(n,k)={n\choose k}2^{-n}$$ (9)

and

$$G(n,k) \equiv R(n,k)F(n,k)={k\over 2(k-n-1)}{n\choose k}2^{-n}$$

$$= -{kn!2^{-n}\over 2(n+1-k)k!(n-k)!}=-{n\choose k-1}2^{-n-1}.$$ (10)

Taking

$$F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)$$ (11)

then gives the alleged identity

$${n+1\choose k}2^{-n-1}-{n\choose k}2^{-n}=-{n\choose k}2^{-n-1}+{n\choose k-1}2^{-n-1}?$$ (12)

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

$$F(0,k)={0\choose k}=\cases{ 1 & for $k=0$\cr 0 & otherwise,\cr}$$ (13)

so $\sum_k F(0,k)=1$ (Petkovsek et al. 1996, pp. 25-27).

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

$$\sum_{n=0}^\infty G(n,0)=\sum_{n=1}^\infty [F(n,n-1)+G(n-1,n-1)]$$ (14)

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

$\sum_{n=0}^\infty G(n,0)=\sum_{n=0}^\infty\left[{F(s(n+1),n)+\sum_{i=0}^{s-1} G(sn+i,n)}\right]$
$-\lim_{n\to\infty}\sum_{k=0}^{n-1} F(sn,k),\quad$	(15)

$$\sum_{k=0}^\infty F(0,k)=\sum_{n=0}^\infty G(n,0)-\lim_{k\to\infty}\sum_{n=0}^k G(n,k),$$ (16)

and

$\sum_{n=0}^\infty G(n,0)=\sum_{n=0}^\infty\left[{\sum_{j=0}^{t-1} F(s(n+1),tn+j)}\right.$
$\left.{+\sum_{i=0}^{s-1}G(sn+i,tn)}\right]-\lim_{n\to\infty}\sum_{k=0}^{n-1} F_{s,t}(n,k),\quad$	(17)

where

$$F_{s,t}(n,k) = \sum_{j=0}^{t-1} F(sn,tk+j)$$ (18)

$$G_{s,t}(n,k) = \sum_{i=0}^{s-1} G(sn+i,tk)$$ (19)

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

See also Apéry's Constant, Convergence Improvement, Zeilberger's Algorithm

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/wilftoc.html#R03. Also available at http://www.math.temple.edu/~zeilberg/mamarim/mamarimhtml/accel.html.

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

Petkovsek, M.; Wilf, H. S.; and Zeilberger, D. ``The WZ Phenomenon.'' Ch. 7 in A=B. Wellesley, MA: A. K. Peters, pp. 121-140, 1996.

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.