6.6.4 Wilf-Zeilberger pairs: wz_certificate
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 you
∑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, you get
and so ∑kF(n,k) does not depend on n, and so is a constant.
The wz_certificate command computes Wilf-Zeilberger pairs.
-
wz_certificate takes four arguments:
-
U(n,k), an expression in two variables.
- res(k), an expression in one
of the variables.
- n and k, the variables.
- wz_certificate(U(n,k),res(k),n,k) returns
the Wilf-Zeilberger certificate R(n,k) for the identity
∑k=−∞infty U(n,k) = res(n).
Example.
To show
Input:
wz_certificate((-1)^k*comb(n,k)*comb(2k,k)*4^(n-k),comb(2n,n),n,k)
Output:
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