.
Wilf–Zeilberger
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 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_{M \to \pm\infty}G(n,M) = 0. \, \)
Together, these conditions ensure that the sum
\( \sum_{k=-\infty}^\infty [F(n+1,k)-F(n,k)] = 0 \)
because the function G telescopes:
\( \begin{align} \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{align} \)
If F and G form a WZ pair, then they satisfy the relation
G(n,k) = R(n,k) F(n,k),
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_{k=0}^\infty (-1)^k {n \choose k} {2k \choose k} 4^{n-k} = {2n \choose n} \)
using the proof certificate
\( R(n,k)=\frac{2k-1}{2n+1}. \)
Define the following functions:
\( \begin{align} 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{align} \)
Now F and G will form a Wilf–Zeilberger pair:
References
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 (04): 508–509.
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.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
