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 was developed by Marko Petkovšek in his PhD-thesis 1992. The algorithm is implemented in all the major computer algebra systems.

Gosper-Petkovšek representation

Let be a field of characteristic zero. A nonzero sequence 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. Let be a nonzero rational function. Then there exist monic polynomials and such that
and
  1. for every nonnegative integer,
  2. and
  3. .
This representation of is called Gosper-Petkovšek normal form. These polynomials can be computed explicitly. This construction of the representation is an essential part of Gosper's algorithm. Petkovšek added the conditions 2. and 3. of this representation which makes this normal form unique.

Algorithm

Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence. The other polynomials can be taken as the monic factors of the first coefficient polynomial resp. the last coefficient polynomial shifted. Then has to fulfill a certain algebraic equation. 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.
In the following pseudocode the degree of a polynomial is denoted by and the coefficient of is denoted by.
algorithm petkovsek is
input: Linear recurrence equation.
output: A hypergeometric solution if there are any hypergeometric solutions.
for each monic divisor of do
for each monic divisor of do
for each do


for each root of do
Find non-zero polynomial solution of
if such a non-zero solution exists then

return a non-zero solution of
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.
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. These rational solutions can be combined to get a particular solution of the inhomogeneous equation. Together with the general solution of the homogeneous problem this gives the general solution of the inhomogeneous problem.

Examples

Signed permutation matrices

The number of signed permutation matrices of size can be described by the sequence which is determined by the recurrence equationover. Taking as monic divisors of respectively, one gets. For the corresponding recurrence equation which is solved in Petkovšek's algorithm isThis recurrence equation has the polynomial solution for an arbitrary. Hence and is a hypergeometric solution. In fact it is the only hypergeometric solution and describes the number of signed permutation matrices.

Irrationality of \zeta(3)

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.