Gosper's algorithm


In mathematics, Gosper's algorithm, due to Bill Gosper, is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose one has a + ... + a = S − S, where S is a hypergeometric term /S; then necessarily a is itself a hypergeometric term, and given the formula for a Gosper's algorithm finds that for S.

Outline of the algorithm

Step 1: Find a polynomial p such that, writing b = a/p, the ratio b/b has the form q/r where q and r are polynomials and no q has a nontrivial factor with r for j = 0, 1, 2, ... .
Step 2: Find a polynomial ƒ such that S = q/p ƒ a. If the series is summable in closed form then clearly a rational function ƒ with this property exists; in fact it must always be a polynomial, and an upper bound on its degree can be found. Determining ƒ is then a matter of solving a system of linear equations.

Relationship to Wilf–Zeilberger pairs

Gosper's algorithm can be used to discover Wilf-Zeilberger pairs, where they exist. Suppose that F − F = G − G where F is known but G is not. Then feed a := F − F into Gosper's algorithm. If it successfully finds S with S − S = a, then we are done: this is the required G. If not, there is no such G.

Definite versus indefinite summation

Gosper's algorithm finds a hypergeometric closed form for the indefinite sum of hypergeometric terms. It can happen that there is no such closed form, but that the sum over all n, or some particular set of values of n, has a closed form. This question is only meaningful when the coefficients are themselves functions of some other variable. So, suppose a is a hypergeometric term in both n and k: that is, a/a and a/a are rational functions of n and k. Then Zeilberger's algorithm and Petkovšek's algorithm may be used to find closed forms for the sum over k of a.

History

discovered this algorithm in the 1970s while working on the Macsyma computer algebra system at SAIL and MIT.