Zeilberger's algorithm

Remarks

If $F(n, k)$ vanishes for $k$ outside a finite range depending on $n$, summing the relation over all $k$ makes the right side a telescoping sum equal to $0$. So $f(n) = \sum_k F(n, k)$ satisfies the recurrence $\sum_{j=0}^{J} a_j(n) f(n + j) = 0$. The search terminates when $F$ is a proper hypergeometric term. Such a term is a polynomial, times a product of factorials of integer-linear forms in $n$ and $k$, times $x^k$. This termination result is part of the fundamental theorem of Wilf and Zeilberger. Example: for $F(n, k) = \binom{n}{k}$ the algorithm stops at $J = 1$ with $a_0 = -2$, $a_1 = 1$ and $G(n, k) = -\binom{n}{k - 1}$. Check by Pascal's rule: $\binom{n + 1}{k} - 2\binom{n}{k} = \binom{n}{k - 1} - \binom{n}{k} = G(n, k + 1) - G(n, k)$, which gives $f(n + 1) = 2f(n)$. Non-example: for $J = 0$ no solution exists here, since that would need $\sum_{j<k}\binom{n}{j}$ to be a hypergeometric term in $k$, and Gosper's algorithm shows it is not.