Previous Up Next

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

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


.

Previous Up Next