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 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 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),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4df98c474d891e70f28c2ab9d611197a24c964c2)
![{\displaystyle \lim _{M\to \pm \infty }G(n,M)=0.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a6b28d70755a5f1909861068110669270880ed9)
Together, these conditions ensure that
![{\displaystyle \sum _{k=-\infty }^{\infty }[F(n+1,k)-F(n,k)]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/32805d72a6813d27800bc28679d4bc9886323aed)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74f2e62d325560fdd668464f8dcd8da05463cc5e)
Therefore,
![{\displaystyle \sum _{k=-\infty }^{\infty }F(n+1,k)=\sum _{k=-\infty }^{\infty }F(n,k),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/261c949f6be8a82c9cd072dfd87cd4f1900a5bf6)
that is
![{\displaystyle \sum _{k=-\infty }^{\infty }F(n,k)={\text{const}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3b8e64aa9788e6425513ba73a6b161c78a032c03)
The constant does not depend on n.
Its value can be found by substituting n = n0
for a particular n0.
If F and G form a WZ pair, then they satisfy the relation
![{\displaystyle G(n,k)=R(n,k)F(n,k-1),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e91240e97e2ee3d9793948349ea15bbc024581bc)
where
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
![{\displaystyle \sum _{k=0}^{\infty }(-1)^{k}{n \choose k}{2k \choose k}4^{n-k}={2n \choose n}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c9733336e3a4c694078356549eb2e6138c2d318b)
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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/52ef18a97e11276f55d64c137028ce341e08256a)
Use the proof certificate
![{\displaystyle R(n,k)={\frac {2k-1}{2n+1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d044d793b05bb1d260ffa83f856afda0a720795b)
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/401dc4cb185c8dea75fe201da54b1b44d4026879)
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.
References
See also
External links