Gosper's algorithm: Difference between revisions

Revision as of 12:45, 20 June 2017

Latest revision as of 17:01, 8 June 2025

(13 intermediate revisions by 10 users not shown)

Line 1:

{{Short description|Summation method for hypergeometric terms}}

In [[mathematics]], '''Gosper's algorithm''' is a procedure for finding sums of [[Hypergeometric identities|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'').

{{Use dmy dates|date=January 2020|cs1-dates=y}}

In [[mathematics]], '''Gosper's algorithm''', due to [[Bill Gosper]], is a procedure for finding sums of [[Hypergeometric identities|hypergeometric terms]] that are themselves hypergeometric terms. That is: suppose weone havehas ''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'').

==Outline of the algorithm==

Line 5 ⟶ 7:

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''&nbsp;+&nbsp;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>{{cite book |author-last1=Petkovšek |author-first1=Marko |author-link1=Marko Petkovšek |url=http://www.math.upenn.edu/~wilf/AeqB.html |title=A&nbsp;=&nbsp;B |author-last2=Wilf |author-first2=Herbert |author-link2=Herbert Wilf |author-last3=Zeilberger |author-first3=Doron |author-link3=Doron Zeilberger |date=1996 |publisher=[[A K Peters Ltd.]] |isbn=1-56881-063-6 |access-date=2020-01-10 |archive-url=https://web.archive.org/web/20190711145429/https://www.math.upenn.edu/~wilf/AeqB.html |archive-date=2019-07-11 |url-status=live}} [https://web.archive.org/web/20190726143843/https://www.math.upenn.edu/~wilf/AeqB.pdf] [https://web.archive.org/web/20200111042729/https://sites.math.rutgers.edu/%7Ezeilberg/AeqB.pdf] [https://web.archive.org/web/20170329070514/http://www.fmf.uni-lj.si/aeqb/AeqB.pdf]</ref>

==Relationship to Wilf&ndash;Zeilberger pairs==

Line 13 ⟶ 15:

==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'',&nbsp;''k'')/''a''(''n''&nbsp;&minus;&nbsp;1,''k'') and ''a''(''n'',&nbsp;''k'')/''a''(''n'',&nbsp;''k''&nbsp;&minus;&nbsp;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'',&nbsp;''k'').

==History==

Line 19 ⟶ 21:

[[Bill Gosper]] discovered this algorithm in the 1970s while working on the [[Macsyma]] computer algebra system at [[Stanford Artificial Intelligence Laboratory|SAIL]] and [[MIT]].

==Further readingNotes==

{{Reflist}}

*[[Marko Petkovšek]], [[Herbert Wilf]] and [[Doron Zeilberger]], ''A&nbsp;=&nbsp;B'', AK Peters 1996, {{isbn|1-56881-063-6}}. Full text online.[http://www.math.upenn.edu/~wilf/AeqB.html]

*[http://www.pnas.org/cgi/reprint/75/1/40.pdf Gosper's 1977 article in PNAS] reporting on the algorithm.

==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]] |___location=Xerox, Palo Alto Research Center, Palo Alto, California, USA |volume=75 |number=1 |pages=40–42 |doi=10.1073/pnas.75.1.40 |pmid=16592483 |pmc=411178 |bibcode=1978PNAS...75...40G |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 |doi-access=free }}

[[Category:Computer algebra]]