   ### 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

 ∑ k
U(n,k) = C res(n)

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

 ∑ k
F(n,k)

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

 N ∑ k=−M
F(n+1,k) −
 N ∑ k=−M
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

 ∑ k
F(n+1,k) =
 ∑ k
F(n,k)

and so ∑kF(n,k) does not depend on n, and so is a constant.

For example, to show

 ∑ k
(−1)k

 n k

 2k k

4nk =

 2n n

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 (

 n k

)(

 2k k

) 4nk/(

 2n n

) 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

 ∑ k
(−1)k

 n k

 2k k

4nk =

 2n n

.   