Petkovšek's algorithm: Difference between revisions

Revision as of 08:58, 27 July 2018

Revision as of 09:18, 27 July 2018

Line 1:

'''Petkovšek's algorithm''' (also '''Hyper''') is a [[computer algebra]] algorithm that computes a basis of [[Hypergeometric identity|hypergeometric terms]] solution of its input [[P-recursive equations|linear recurrence equation with polynomial coefficients]]. Equivalently, it computes a first order right factor of linear [[Difference operator|difference operators]] with polynomial coefficients. This algorithm was developed by [[Marko Petkovšek]] in his PhD-thesis 1992.<ref name=":0">{{Cite journal|last=Petkovšek|first=Marko|date=1992|title=Hypergeometric solutions of linear recurrences with polynomial coefficients|url=http://linkinghub.elsevier.com/retrieve/pii/0747717192900386|journal=Journal of Symbolic Computation|volume=14|issue=2-3|pages=243–264|doi=10.1016/0747-7171(92)90038-6|issn=0747-7171|via=}}</ref> The algorithm is implemented in all the major computer algebra systems.

== Gosper-Petkovšek representation ==

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