info prev up next book cdrom email home

Wilf-Zeilberger Pair

A pair of Closed Form functions $(F,G)$ is said to be a Wilf-Zeilberger pair if

\begin{displaymath}
F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k).
\end{displaymath} (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

\begin{displaymath}
\sum_k t(n,k)=\mathop{\rm rhs}(n)
\end{displaymath} (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
\begin{displaymath}
\sum_k F(n,k)=1,
\end{displaymath} (3)

where
\begin{displaymath}
F(n,k)\equiv {t(n,k)\over\mathop{\rm rhs}(n)}.
\end{displaymath} (4)

Now use a Rational Function $R(n,k)$ provided by Zeilberger's Algorithm, define
\begin{displaymath}
G(n,k)\equiv R(n,k)F(n,k).
\end{displaymath} (5)

The identity (1) then results. Summing the relation over all integers then telescopes the right side to 0, giving
\begin{displaymath}
\sum_k F(n+1,k)=\sum_k F(n,k).
\end{displaymath} (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

\begin{displaymath}
\sum_{k=0}^n {n\choose k}=2^n,
\end{displaymath} (7)

the function $R(n,k)$ returned by Zeilberger's Algorithm is
\begin{displaymath}
R(n,k)={k\over 2(k-n-1)}.
\end{displaymath} (8)

Therefore,
\begin{displaymath}
F(n,k)={n\choose k}2^{-n}
\end{displaymath} (9)

and
$\displaystyle G(n,k)$ $\textstyle \equiv$ $\displaystyle R(n,k)F(n,k)={k\over 2(k-n-1)}{n\choose k}2^{-n}$  
  $\textstyle =$ $\displaystyle -{kn!2^{-n}\over 2(n+1-k)k!(n-k)!}=-{n\choose k-1}2^{-n-1}.$  
      (10)

Taking
\begin{displaymath}
F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)
\end{displaymath} (11)

then gives the alleged identity


\begin{displaymath}
{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}?
\end{displaymath} (12)

Expanding and evaluating shows that the identity does actually hold, and it can also be verified that
\begin{displaymath}
F(0,k)={0\choose k}=\cases{
1 & for $k=0$\cr
0 & otherwise,\cr}
\end{displaymath} (13)

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


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

\begin{displaymath}
\sum_{n=0}^\infty G(n,0)=\sum_{n=1}^\infty [F(n,n-1)+G(n-1,n-1)]
\end{displaymath} (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)

\begin{displaymath}
\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),
\end{displaymath} (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
$\displaystyle F_{s,t}(n,k)$ $\textstyle =$ $\displaystyle \sum_{j=0}^{t-1} F(sn,tk+j)$ (18)
$\displaystyle G_{s,t}(n,k)$ $\textstyle =$ $\displaystyle \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.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26