A pair of Closed Form functions
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}](w_994.gif) |
(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}](w_995.gif) |
(2) |
for which the Summand
vanishes for all
outside some finite interval. Now divide by the right-hand side to obtain
![\begin{displaymath}
\sum_k F(n,k)=1,
\end{displaymath}](w_997.gif) |
(3) |
where
![\begin{displaymath}
F(n,k)\equiv {t(n,k)\over\mathop{\rm rhs}(n)}.
\end{displaymath}](w_998.gif) |
(4) |
Now use a Rational Function
provided by Zeilberger's Algorithm, define
![\begin{displaymath}
G(n,k)\equiv R(n,k)F(n,k).
\end{displaymath}](w_1000.gif) |
(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}](w_1001.gif) |
(6) |
Therefore,
is independent of
, and so must be a constant. If
is properly normalized, then
it will be true that
.
For example, consider the Binomial Coefficient identity
![\begin{displaymath}
\sum_{k=0}^n {n\choose k}=2^n,
\end{displaymath}](w_1004.gif) |
(7) |
the function
returned by Zeilberger's Algorithm is
![\begin{displaymath}
R(n,k)={k\over 2(k-n-1)}.
\end{displaymath}](w_1005.gif) |
(8) |
Therefore,
![\begin{displaymath}
F(n,k)={n\choose k}2^{-n}
\end{displaymath}](w_1006.gif) |
(9) |
and
Taking
![\begin{displaymath}
F(n+1,k)-F(n,k)=G(n,k+1)-G(n,k)
\end{displaymath}](w_1010.gif) |
(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}](w_1011.gif) |
(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}](w_1012.gif) |
(13) |
so
(Petkovsek et al. 1996, pp. 25-27).
For any Wilf-Zeilberger pair
,
![\begin{displaymath}
\sum_{n=0}^\infty G(n,0)=\sum_{n=1}^\infty [F(n,n-1)+G(n-1,n-1)]
\end{displaymath}](w_1013.gif) |
(14) |
whenever either side converges (Zeilberger 1993). In addition,
|
|
|
(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}](w_1016.gif) |
(16) |
and
|
|
|
(17) |
where
(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.
© 1996-9 Eric W. Weisstein
1999-05-26