Gosper's algorithm: Difference between revisions

Revision as of 08:09, 12 July 2023

Revision as of 07:22, 6 February 2024

Line 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-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 |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]</ref>

|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]</ref>

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

Line 22 ⟶ 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]].

==ReferencesNotes==

{{Reflist}}

==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 }}