Gosper's algorithm: Difference between revisions

Revision as of 17:18, 5 August 2019

Revision as of 04:45, 11 January 2020

Line 1:

{{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 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]] 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'').

Line 20 ⟶ 21:

==Further reading==

* {{cite book |author-first1=Marko |author-last1=Petkovšek |author-link1=Marko Petkovšek |author-first2=Herbert |author-last2=Wilf |author-link2=Herbert Wilf |author-first3=Doron |author-last3=Zeilberger |author-link3=Doron Zeilberger

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

|work=Home Page for the Book "A=B" <!-- |contribution=Foreword |contributor-first=Donald E. |contributor-last=Knuth |contributor-link=Donald E. Knuth --> |title=A&nbsp;=&nbsp;B |publisher=[[A K Peters Ltd.]] |date=1996 |isbn=1-56881-063-6 |url=http://www.math.upenn.edu/~wilf/AeqB.html |access-date=2020-01-10 |url-status=live |archive-url=https://web.archive.org/web/20190711145429/https://www.math.upenn.edu/~wilf/AeqB.html |archive-date=2019-07-11}} [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]

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

* {{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]] (PNAS) |___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}}

[[Category:Computer algebra]]