Previous Up Next

12.1.4  Wilf-Zeilberger pairs

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

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, you 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.

The wz_certificate command computes Wilf-Zeilberger pairs.

Example

To show that

 
k
 (−1)k 


n
k




2k
k


4nk=


2n
n


,     (1)

input:

wz_certificate((-1)^k*comb(n,k)*comb(2k,k)*4^(n-k),comb(2n,n),n,k)
     
k−1
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) form 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, we have ∑k F(0,k)=1 and so ∑k F(n,k)=1 for all n, implying (1).


Previous Up Next