Exercise 2095Combinatorics › Binomial coefficientsM1Added 3 Nov 2026

Zeilberger's algorithm (statement)

#Zeilberger#creative telescoping#binomial

Statement

Describe Zeilberger's algorithm for proving binomial identities.

Hint

The algorithm finds a recurrence in $n$ for $S(n)=\sum_k F(n,k)$ , then verifies it.

Show solutionHide solution

Solution

Idea. For a proper hypergeometric term $F(n,k)$ , find a linear recurrence $a_0(n)S(n)+\cdots+a_r(n)S(n+r)=0$ , by finding polynomials $a_i(n)$ and a rational function $R(n,k)$ such that
$\sum_i a_i(n)F(n+i,k)=G(n,k+1)-G(n,k)$
(telescoping in $k$ ).

Conclusion. Zeilberger's algorithm (creative telescoping) systematically proves binomial identities and provides certificates.

Zeilberger's algorithm (statement)

Statement

Solution

More problems in Binomial coefficients