## § WZ (Wilf Zeilberger) pairs

- Suppose we want to find a closed form for $\sum_{k=-\infty}^\infty F(n, k)$.
- If we can show that $\sum_{k=-\infty}^{\infty} F(n, k) = \sum_{k=-\infty}^{\infty} F(n + 1, k)$, then we have that $\sum_{k=-infty}^{infty} F(n, k) = \sum_{k=-infty}^{\infty} F(0, k)$. So this will be independent of $n$, and we can find a closed form that is independent of $k$, so we can get a concrete numeric value.
- Now, the question then becomes, how do we show that $\sum_{k=-\infty}^{\infty} F(n, k) = \sum_{k=-\infty}^{\infty} F(n + 1, k)$?
- We can rewrite it as $\sum_{k=-\infty}^{\infty} (F(n+1, k) - F(n , k)) = 0$
- Since we're doing wishful thinking, let's wish that the sum telescoes in $k$!
- So we ask that there's a function $G(n, k)$, such that $F(n + 1, k) - F(n, k) = G(n, k+1) - G(n, k)$, and that $\lim_{K \to \pm \infty} G(K) = 0$, so $G$ vanishes at the boundary. This forces the sum to be identically zero.
- This gives us the sum to telescope, as $\sum_{k=-\infty}^{\infty} F(n+1, k) - F(n, k) = \sum_{k=-\infty}^{\infty} G(n, k+1) - G(n, k)$.
- We write the RHS as $lim_{M \to \infty} \sum_{k=-M}^{M} G(n, k + 1) - G(n, k)$. But that equals $\lim_{M \to \infty} (G(n, M+1) - G(n, -M))$. But both these terms vanish at the limit, so we get $0 - 0 = 0$.
- Thus, we see that we've checked that $\sum_k F(n + 1, k) - F(n, k) = 0$ by showing that $\sum_k G(n, k+1) - G(n, k)$ vanishes.
- If $F, G$ form a WZ pair, there is a rationl function $R$ such that $G(n, k) = R(n, k) F(n, k - 1)$. $R(n, k)$ is the certificate.
- See that we are computing an
*indefinite * sum for $\sum_k F(n, k)$, like an indefinite integral.

#### § Certificate for $F, G$.

- It will turn out that the $G(n, k)$ will always be of the form $G(n, k) = R(n, k) F(n, k - 1)$, since Gosper's algorithm always finds such as $G(n, k)$! So, the $R(n, k)$ forms a certificate, where we check that the corresponding $G(n, k)$ obeys the two identities above.

#### § References

- Generatingfunctionlogy
- A = B
- Concrete Mathematics