---
tag: 4HP429BZQ5
kind: definition
name: WZ theory
msc: [05A19, 33F10]
defines: 8FK88MNE0N
uses: [0GBZM0MT0F]
sources:
  - url: https://en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_pair
---

## Definition

Let $F(n, k)$ and $G(n, k)$ be functions defined for integers $n \ge 0$ and $k$.
The pair $(F, G)$ is a *WZ pair* if, for all $n$ and $k$,
$$F(n + 1, k) - F(n, k) = G(n, k + 1) - G(n, k).$$
The *WZ method* proves an identity $\sum_k f(n, k) = r(n)$, with $r(n) \ne 0$, in three steps:

1. set $F(n, k) = f(n, k) / r(n)$, so the identity reads $\sum_k F(n, k) = 1$;
2. give a rational function $R(n, k)$, the *WZ certificate*, such that $(F, G)$ with $G = R F$ is a WZ pair;
3. check that $\sum_k F(0, k) = 1$ and that $G(n, k) \to 0$ as $k \to \pm\infty$ for each $n$.

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