Petkovšek's algorithm: Difference between revisions

Revision as of 08:56, 27 July 2018

Revision as of 08:58, 27 July 2018

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 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=MarkoPetkovšek|first=PetkovšekMarko|last2=Wilf|first2=Herbert S.|last3=Zeilberger|first3=Doron|date=1996|publisher=A K Peters|others=|year=|isbn=1568810636|___location=|pages=|oclc=33898705}}</ref><ref>{{Cite book|url=https://www.worldcat.org/oclc/701369215|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=|year=|isbn=9783709104453|___location=Wien|pages=|oclc=701369215}}</ref><p>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>.</p>

<b>algorithm</b> petkovsek <b>is</b>

'''input:''' Linear recurrence equation <math display="inline">\sum_{k=0}^r p_k(n) \, y (n+k) = 0, p_k \in \mathbb{K}[n], p_0, p_r \neq 0</math>.