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
for every nonnegative integer ,
and
.
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.[2] Petkovšek added the conditions 2. and 3. of this representation which makes this normal form unique.[1]
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.[1][3][4]
In the following pseudocode the degree of a polynomial is denoted by and the coefficient of is denoted by .
algorithm petkovsek isinput: Linear recurrence equation .
output: A hypergeometric solution if there are any hypergeometric solutions.
for each monic divisor of dofor each monic divisor of dofor eachdofor each root of do
Find non-zero polynomial solution of if such a non-zero solution exists thenreturn 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.[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. 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.[1]
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 (up to a constant) the only hypergeometric solution and describes the number of signed permutation matrices.[5]
Irrationality of
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.[3]