mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, Gosper's algorithm, due to

Bill Gosper Ralph William Gosper Jr. (born April 26, 1943), known as Bill Gosper, is an American mathematician and programmer. Along with Richard Greenblatt, he may be considered to have founded the hacker community, and he holds a place of pride in the ...

, is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose one has ''a''(1) + ... + ''a''(''n'') = ''S''(''n'') − ''S''(0), where ''S''(''n'') is a hypergeometric term (i.e., ''S''(''n'' + 1)/''S''(''n'') is a

rational function In mathematics, a rational function is any function that can be defined by a rational fraction, which is an algebraic fraction such that both the numerator and the denominator are polynomials. The coefficients of the polynomials need not be rat ...

of ''n''); then necessarily ''a''(''n'') is itself a hypergeometric term, and given the formula for ''a''(''n'') Gosper's algorithm finds that for ''S''(''n'').

Outline of the algorithm

Step 1: Find a polynomial ''p'' such that, writing ''b''(''n'') = ''a''(''n'')/''p''(''n''), the ratio ''b''(''n'')/''b''(''n'' − 1) has the form ''q''(''n'')/''r''(''n'') where ''q'' and ''r'' are polynomials and no ''q''(''n'') has a nontrivial factor with ''r''(''n'' + ''j'') for ''j'' = 0, 1, 2, ... . (This is always possible, whether or not the series is summable in closed form.) Step 2: Find a polynomial ''ƒ'' such that ''S''(''n'') = ''q''(''n'' + 1)/''p''(''n'') ''ƒ''(''n'') ''a''(''n''). 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 ''ƒ'' (or finding that there is no such ''ƒ'') is then a matter of solving a system of linear equations.
/ref>

Relationship to Wilf–Zeilberger pairs

Gosper's algorithm can be used to discover

Wilf–Zeilberger pair In mathematics, specifically combinatorics, a Wilf–Zeilberger pair, or WZ pair, is a pair of functions that can be used to certify certain combinatorial identities ...

s, where they exist. Suppose that ''F''(''n'' + 1, ''k'') − ''F''(''n'', ''k'') = ''G''(''n'', ''k'' + 1) − ''G''(''n'', ''k'') where ''F'' is known but ''G'' is not. Then feed ''a''(''k'') := ''F''(''n'' + 1, ''k'') − ''F''(''n'', ''k'') into Gosper's algorithm. (Treat this as a function of k whose coefficients happen to be functions of n rather than numbers; everything in the algorithm works in this setting.) If it successfully finds ''S''(''k'') with ''S''(''k'') − ''S''(''k'' − 1) = ''a''(''k''), then we are done: this is the required ''G''. If not, there is no such ''G''.

Definite versus indefinite summation

Gosper's algorithm finds (where possible) 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(n,k) is a hypergeometric term in both ''n'' and ''k'': that is, ''a''(''n'', ''k'')/''a''(''n'' − 1,''k'') and ''a''(''n'', ''k'')/''a''(''n'', ''k'' − 1) are rational functions of ''n'' and ''k''. Then Zeilberger's algorithm and

Petkovšek's algorithm Petkovšek's algorithm (also Hyper) is a computer algebra algorithm that computes a basis of hypergeometric terms solution of its input linear recurrence equation with polynomial coefficients. Equivalently, it computes a first order right factor ...

may be used to find closed forms for the sum over ''k'' of ''a''(''n'', ''k'').

History

discovered this algorithm in the 1970s while working on the

Macsyma Macsyma (; "Project MAC's SYmbolic MAnipulator") is one of the oldest general-purpose computer algebra systems still in wide use. It was originally developed from 1968 to 1982 at MIT's Project MAC. In 1982, Macsyma was licensed to Symbolics and ...

computer algebra system at SAIL and

MIT The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of the m ...

References

* {{cite journal , title=Decision procedure for indefinite hypergeometric summation , author-first=Ralph William "Bill" , author-last=Gosper, Jr. , author-link=Bill Gosper , date=January 1978 , orig-year=1977-09-26 , series=Mathematics , journal=

Proceedings of the National Academy of Sciences of the United States of America ''Proceedings of the National Academy of Sciences of the United States of America'' (often abbreviated ''PNAS'' or ''PNAS USA'') is a peer-reviewed multidisciplinary scientific journal. It is the official journal of the National Academy of Scien ...

, location=Xerox, Palo Alto Research Center, Palo Alto, California, USA , volume=75 , number=1 , pages=40–42 , url=http://www.pnas.org/cgi/reprint/75/1/40.pdf , access-date=2020-01-10 , url-status=live , archive-url=https://web.archive.org/web/20190412200118/https://www.pnas.org/content/pnas/75/1/40.full.pdf , archive-date=2019-04-12 , quote=algorithm / binomial coefficient identities / closed form / symbolic computation / linear recurrences Computer algebra Hypergeometric functions