Petkovšek's algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Petkovšek's algorithm is a computer algebra algorithm that computes a basis of hypergeometric terms solution of its input linear recurrence equation with polynomial coefficients. Equivalently, it computes a first order right factor of linear difference operators with polynomial coefficients. This algorithm is implemented in all the major computer algebra systems.


  • Given the linear recurrence

the algorithm finds two linearly independent hypergeometric terms that are solution:

(Here, denotes Euler's Gamma function.) Note that the second solution is also a binomial coefficient , but it is not the aim of this algorithm to produce binomial expressions.

  • Given the sum

coming from Apéry's proof of the irrationality of , Zeilberger's algorithm computes the linear recurrence

Given this recurrence, the algorithm does not return any hypergeometric solution, which proves that does not simplify to a hypergeometric term.

See also[edit]

Marko Petkovšek