Gosper's algorithm
Encyclopedia
In mathematics
, Gosper's algorithm is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose we have 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
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).
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.
discovered this algorithm in the 1970s while working on the Macsyma
computer algebra system at SAIL and MIT.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, Gosper's algorithm is a procedure for finding sums of hypergeometric terms that are themselves hypergeometric terms. That is: suppose we have 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
Rational function
In mathematics, a rational function is any function which can be written as the ratio of two polynomial functions. Neither the coefficients of the polynomials nor the values taken by the function are necessarily rational.-Definitions:...
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.
Relationship to Wilf–Zeilberger pairs
Gosper's algorithm can be used to discover Wilf–Zeilberger pairs, 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 may be used to find closed forms for the sum over k of a(n, k).History
Bill GosperBill Gosper
Ralph William Gosper, Jr. , known as Bill Gosper, is an American mathematician and programmer from Pennsauken Township, New Jersey...
discovered this algorithm in the 1970s while working on the Macsyma
Macsyma
Macsyma is a computer algebra system that was originally developed from 1968 to 1982 at MIT as part of Project MAC and later marketed commercially...
computer algebra system at SAIL and MIT.
Further reading
- Marko PetkovsekMarko PetkovšekMarko Petkovšek is a Slovenian mathematician, born: 1955, working mainly in symbolic computation.He is a professor of discrete and computational mathematics at the University of Ljubljana. He completed his Ph.D. at Carnegie Mellon University...
, Herbert WilfHerbert WilfHerbert Saul Wilf is a mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylvania. He has written numerous books and research papers...
and Doron ZeilbergerDoron ZeilbergerDoron Zeilberger is an Israeli mathematician, known for his work in combinatorics.He is a Board of Governors Professor of Mathematics at Rutgers University...
, A = B, AK Peters 1996, ISBN 1568810636. Full text online.http://www.math.upenn.edu/~wilf/AeqB.html - Gosper's 1977 article in PNAS reporting on the algorithm.