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

- 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

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.

- 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=−∞+∞ U(n,k)=res(n).

#### Example

To show that

∑
k

(−1)k

⎛
⎜
⎝

n
k

⎞
⎟
⎠

⎛
⎜
⎝

2k
k

⎞
⎟
⎠

4n−k=

⎛
⎜
⎝

2n
n

⎞
⎟
⎠

, (1)

input:

wz_certificate((-1)^k*comb(n,k)*comb(2 k,k)*4^(n-k),comb(2 n,n),n,k)

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

) 4n−k/(

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