Petkovšek's algorithm

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. The algorithm is implemented in all the major computer algebra systems.

Gosper-Petkovšek representation

Let [math]\displaystyle{ \mathbb{K} }[/math] be a field of characteristic zero. A nonzero sequence [math]\displaystyle{ y(n) }[/math] is called hypergeometric if the ratio of two consecutive terms is rational, i.e. [math]\displaystyle{ y (n+1) /y(n) \in \mathbb{K}(n) }[/math]. The Petkovšek algorithm uses as key concept that this rational function has a specific representation, namely the Gosper-Petkovšek normal form. Let [math]\displaystyle{ r(n) \in \mathbb{K}[n] }[/math] be a nonzero rational function. Then there exist monic polynomials [math]\displaystyle{ a, b, c \in \mathbb{K} [n] }[/math] and [math]\displaystyle{ 0 \neq z \in \mathbb{K} }[/math] such that

[math]\displaystyle{ r(n) = z \frac{a(n)}{b(n)} \frac{c(n+1)}{c(n)} }[/math]

and

1. [math]\displaystyle{ \gcd (a(n), b(n+k)) = 1 }[/math] for every nonnegative integer [math]\displaystyle{ k \in \N }[/math],
2. [math]\displaystyle{ \gcd (a(n), c(n))=1 }[/math] and
3. [math]\displaystyle{ \gcd ( b(n), c(n+1))=1 }[/math].

This representation of [math]\displaystyle{ r(n) }[/math] 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 [math]\displaystyle{ c(n) }[/math]. The other polynomials [math]\displaystyle{ a(n),b(n) }[/math] can be taken as the monic factors of the first coefficient polynomial [math]\displaystyle{ p_0 (n) }[/math] resp. the last coefficient polynomial shifted [math]\displaystyle{ p_r(n-r+1) }[/math]. Then [math]\displaystyle{ z }[/math] has to fulfill a certain algebraic equation. Taking all the possible finitely many triples [math]\displaystyle{ (a(n), b(n), z) }[/math] and computing the corresponding polynomial solution of the transformed recurrence equation [math]\displaystyle{ c(n) }[/math] gives a hypergeometric solution if one exists.

In the following pseudocode the degree of a polynomial [math]\displaystyle{ p(n) \in \mathbb{K}[n] }[/math] is denoted by [math]\displaystyle{ \deg (p (n)) }[/math] and the coefficient of [math]\displaystyle{ n^d }[/math] is denoted by [math]\displaystyle{ \text{coeff} ( p(n), n^d ) }[/math].

algorithm petkovsek is
    input: Linear recurrence equation [math]\displaystyle{ \sum_{k=0}^r p_k(n) \, y (n+k) = 0, p_k \in \mathbb{K}[n], p_0, p_r \neq 0 }[/math].
    output: A hypergeometric solution [math]\displaystyle{ y }[/math] if there are any hypergeometric solutions.

    for each monic divisor [math]\displaystyle{ a(n) }[/math] of [math]\displaystyle{ p_0(n) }[/math] do
        for each monic divisor [math]\displaystyle{ b(n) }[/math] of [math]\displaystyle{ p_r(n-r+1) }[/math] do
            for each [math]\displaystyle{ k=0,\dots,r }[/math] do
                [math]\displaystyle{ \tilde{p}_k (n)= p_k (n) \prod_{j=0}^{k-1} a(n+j) \prod_{i=k}^{r-1} b(n+i) }[/math]
        [math]\displaystyle{ d = \max_{k=0,\dots,r} \deg (\tilde{p}_k (n)) }[/math]
        for each root [math]\displaystyle{ z }[/math] of [math]\displaystyle{ \sum_{k=0}^r \text{coeff} (\tilde{p}_k (n), n^d ) z^k }[/math] do
            Find non-zero polynomial solution [math]\displaystyle{ c(n) }[/math] of [math]\displaystyle{ \sum_{k=0}^r z^k \,\tilde{p}_k(n) \, c(n+k)=0 }[/math]
            if such a non-zero solution [math]\displaystyle{ c(n) }[/math] exists then
                [math]\displaystyle{ r(n)=z \, a(n)/b(n) \, c(n+1)/c(n) }[/math]
                return a non-zero solution [math]\displaystyle{ y (n) }[/math] of [math]\displaystyle{ y (n+1) = r(n) \, y (n) }[/math]

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 [math]\displaystyle{ n \times n }[/math] can be described by the sequence [math]\displaystyle{ y(n) }[/math] which is determined by the recurrence equation[math]\displaystyle{ 4 (n+1)^2 \, y(n) + 2 \, y(n+1) + (-1) \, y(n+2) = 0 }[/math]over [math]\displaystyle{ \Q }[/math]. Taking [math]\displaystyle{ a(n) = n+1,b(n)=1 }[/math] as monic divisors of [math]\displaystyle{ p_0 (n) = 4(n+1)^2, p_2(n) = -1 }[/math] respectively, one gets [math]\displaystyle{ z = \pm 2 }[/math]. For [math]\displaystyle{ z=2 }[/math] the corresponding recurrence equation which is solved in Petkovšek's algorithm is[math]\displaystyle{ 4(n+1)^2 \, c(n) + 4(n+1)\, c(n+1) - 4(n+1)(n+2) \, c(n+2) = 0. }[/math]This recurrence equation has the polynomial solution [math]\displaystyle{ c(n) = c_0 }[/math] for an arbitrary [math]\displaystyle{ c_0 \in \Q }[/math]. Hence [math]\displaystyle{ r(n)=2 (n+1) }[/math] and [math]\displaystyle{ y(n) = 2^n \, n! }[/math] is a hypergeometric solution. In fact it is (up to a constant) the only hypergeometric solution and describes the number of signed permutation matrices.

Irrationality of [math]\displaystyle{ \zeta(3) }[/math]

Given the sum

[math]\displaystyle{ a(n)=\sum_{k=0}^n{\binom{n}{k}^2\binom{n+k}{k}^2}, }[/math]

coming from Apéry's proof of the irrationality of [math]\displaystyle{ \zeta(3) }[/math], Zeilberger's algorithm computes the linear recurrence

[math]\displaystyle{ (n+2)^3 \, a(n+2)-(17n^2+51n+39)(2n+3) \, a(n+1)+(n+1)^3 \, a(n)=0. }[/math]

Given this recurrence, the algorithm does not return any hypergeometric solution, which proves that [math]\displaystyle{ a(n) }[/math] does not simplify to a hypergeometric term.