5.7.5 Wilf-Zeilberger pairs: wz_certificate
The wz_certificate takes four arguments; an expression
U(n,k) in two variables, an expression res(k) in one of the
variables, the variable n and the variable k.
wz_certificate returns the Wilf-Zeilberger certificate
R(n,k) for the identity
sum(U(n,k),k=-infinity..+infinity) = res(n).
The Wilf-Zeilberger certificate R(n,k) is used to prove the identity
for some constant C (typically 1) whose value can be determined by
evaluating both sides for some value of k. To see how that works,
note that the above identity is equivalent to
being constant, where F(n,k) = U(n,k)/res(n). The Wilf-Zeilberger
certificate is a rational function R(n,k) that make F(n,k) and
G(n,k) = R(n,k) F(n,k) a Wilf-Zeilberger pair, meaning
-
F(n+1,k) − F(n,k) = G(n,k+1) − G(n,k) for integers n ≥
0, k.
- limk → ±∞ G(n,k) = 0 for each n≥ 0.
To see how this helps, adding the first equation from k=−M to k=N
gives us
∑k=−MN(F(n+1,k)−F(n,k)) = ∑k=−MN(G(n,k+1) −
G(n,k)). The right-hand side is a telescoping series, and so the
equality can be written
| F(n+1,k) − | | F(n,k) =
G(n,N+1)−G(n,−M). |
Taking the limit as N,M → ∞ and using the second condition of
Wilf-Zeilberger pairs, we get
and so ∑kF(n,k) does not depend on n, and so is a constant.
For example, to show
Input:
wz_certificate((-1)^k*comb(n,k)*comb(2k,k)*4^(n-k),comb(2n,n),n,k)
Output:
(2*k-1)/(2*n+1)
This means that R(n,k) = (2k−1)/(2n+1) is a Wilf-Zeilberger
certificate; in other words
F(n,k) = (−1)k (
)(
) 4n−k/(
) and
G(n,k) = R(n,k)F(n,k) are a Wilf-Zeilberger pair. So
∑k F(n,k) is a constant. Since F(0,0)=1 and F(0,k) = 0
for k>0,
∑k F(0,k) = 1
and so ∑k F(n,k) = 1 for all n, showing