§ 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