Petkovšek's algorithm: Difference between revisions

Revision as of 12:45, 3 August 2019

Revision as of 09:15, 30 December 2020

Line 15:

== 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|last=Petkovšek|first=Marko|last2=Wilf|first2=Herbert S.|last3=Zeilberger|first3=Doron|date=1996|publisher=A K Peters|others=|isbn=1568810636|___location=|pages=|oclc=33898705}}</ref><ref>{{Cite book|title=The concrete tetrahedron : symbolic sums, recurrence equations, generating functions, asymptotic estimates|last=Kauers|first=Manuel|last2=Paule|first2=Peter|date=2011|publisher=Springer|others=|isbn=9783709104453|___location=Wien|pages=|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>.