Petkovšek's algorithm: Difference between revisions

Revision as of 09:16, 5 July 2021

Latest revision as of 15:01, 13 September 2021

Line 12:

#<math display="inline">\gcd ( b(n), c(n+1))=1</math>.

This representation of <math display="inline">r(n)</math> is called Gosper-Petkovšek normal form. These polynomials can be computed explicitly. This construction of the representation is an essential part of [[Gosper's algorithm]].<ref>{{Cite journal |last=Gosper |first=R. William |date=1978 |title=Decision procedure for indefinite hypergeometric summation |url=https://pdfs.semanticscholar.org/c66e/0beca13f866f748971d18bd39ebdc2b88751.pdf |archive-url=https://web.archive.org/web/20180727145550/https://pdfs.semanticscholar.org/c66e/0beca13f866f748971d18bd39ebdc2b88751.pdf |url-status=dead |archive-date=2018-07-27 |journal=[[Proc. Natl. Acad. Sci. USA]] |volume=75 |issue=1 |pages=40–42|doi=10.1073/pnas.75.1.40 |pmid=16592483 |pmc=411178 |s2cid=26361864 |doi-access=free }}</ref> Petkovšek added the conditions 2. and 3. of this representation which makes this normal form unique.<ref name=":0" />

== Algorithm ==

Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence <math display="inline">c(n)</math>. The other polynomials <math display="inline">a(n),b(n)</math> can be taken as the monic factors of the first coefficient polynomial <math display="inline">p_0 (n)</math> resp. the last coefficient polynomial shifted <math display="inline">p_r(n-r+1)</math>. Then <math display="inline">z</math> has to fulfill a certain [[algebraic equation]]. Taking all the possible finitely many triples <math display="inline">(a(n), b(n), z)</math> and computing the corresponding [[Polynomial solutions of P-recursive equations|polynomial solution]] of the transformed recurrence equation <math display="inline">c(n)</math> gives a hypergeometric solution if one exists.<ref name=":0" /><ref name=":1">{{Cite book|url=https://www.math.upenn.edu/~wilf/Downld.html|title=A=B|lastlast1=Petkovšek|firstfirst1=Marko|last2=Wilf|first2=Herbert S.|last3=Zeilberger|first3=Doron|date=1996|publisher=A K Peters|isbn=1568810636|oclc=33898705}}</ref><ref>{{Cite book|title=The concrete tetrahedron : symbolic sums, recurrence equations, generating functions, asymptotic estimates|lastlast1=Kauers|firstfirst1=Manuel|last2=Paule|first2=Peter|date=2011|publisher=Springer|isbn=9783709104453|___location=Wien|oclc=701369215}}</ref>

In the following pseudocode the degree of a polynomial <math display="inline">p(n) \in \mathbb{K}[n]</math> is denoted by <math display="inline">\deg (p (n))</math> and the coefficient of <math display="inline">n^d</math> is denoted by <math display="inline">\text{coeff} ( p(n), n^d )</math>.