Petkovšek's algorithm (also Hyper) 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 was developed by Marko Petkovšek in his PhD-thesis 1992.
[1] The algorithm is implemented in all the major computer algebra systems.
is called hypergeometric if the ratio of two consecutive terms is rational, i.e.
The Petkovšek algorithm uses as key concept that this rational function has a specific representation, namely the Gosper-Petkovšek normal form.
be a nonzero rational function.
Then there exist monic polynomials
is called Gosper-Petkovšek normal form.
This construction of the representation is an essential part of Gosper's algorithm.
[2] Petkovšek added the conditions 2. and 3. of this representation which makes this normal form unique.
[1] Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence
can be taken as the monic factors of the first coefficient polynomial
the last coefficient polynomial shifted
Taking all the possible finitely many triples
and computing the corresponding polynomial solution of the transformed recurrence equation
gives a hypergeometric solution if one exists.
[1][3][4] In the following pseudocode the degree of a polynomial
If one does not end if a solution is found it is possible to combine all hypergeometric solutions to get a general hypergeometric solution of the recurrence equation, i.e. a generating set for the kernel of the recurrence equation in the linear span of hypergeometric sequences.
[1] Petkovšek also showed how the inhomogeneous problem can be solved.
He considered the case where the right-hand side of the recurrence equation is a sum of hypergeometric sequences.
After grouping together certain hypergeometric sequences of the right-hand side, for each of those groups a certain recurrence equation is solved for a rational solution.
Together with the general solution of the homogeneous problem this gives the general solution of the inhomogeneous problem.
[1] The number of signed permutation matrices of size
the corresponding recurrence equation which is solved in Petkovšek's algorithm is
This recurrence equation has the polynomial solution
In fact it is (up to a constant) the only hypergeometric solution and describes the number of signed permutation matrices.
[5] 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.