Petkovšek's algorithm
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.
Examples
- 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.
References
- Template:Cite article
- Template:Cite article
- Template:Cite article
- Petkovsek, Marko; Wilf, Herbert; Zeilberger, Doron (1996). "A = B".
- Template:Cite article
- Template:Cite article
- Template:Cite article
- Template:Cite article