WZ theory

Remarks

Why it works: summing the WZ equation over all $k$ makes the right side telescope to $0$. So $\sum_k F(n + 1, k) = \sum_k F(n, k)$ for all $n$, and the sum stays equal to its value $1$ at $n = 0$. When $F$ is a hypergeometric term, the WZ equation divided by $F(n, k)$ becomes an identity of rational functions, which is checked by algebra.

Example: the identity $\sum_k \binom{n}{k} = 2^n$ gives $F(n, k) = \binom{n}{k} / 2^n$. The certificate is $R(n, k) = -\frac{k}{2(n - k + 1)}$, so $G(n, k) = -\binom{n}{k-1} / 2^{n+1}$. Both sides of the WZ equation equal $\big(\binom{n}{k-1} - \binom{n}{k}\big) / 2^{n+1}$, by Pascal's rule. Also $G(n, k) = 0$ outside $1 \le k \le n + 1$, and $\sum_k F(0, k) = 1$.

Non-example: for $F(n, k) = \binom{n}{k} / 2^n$, the choice $G = 0$ does not give a WZ pair. The equation would require $F(n + 1, k) = F(n, k)$, which fails for $n = 0$ and $k = 1$, since $1/2 \ne 0$.

The Wilf–Zeilberger pair node treats the pairs themselves in more detail.