Petkovšek's algorithm

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

${\displaystyle r(n)=z{\frac {a(n)}{b(n)}}{\frac {c(n+1)}{c(n)}}}$

and

1. ${\textstyle \gcd(a(n),b(n+k))=1}$ for every nonnegative integer ${\textstyle k\in \mathbb {N} }$,
2. ${\textstyle \gcd(a(n),c(n))=1}$ and
3. ${\textstyle \gcd(b(n),c(n+1))=1}$.

This representation of ${\textstyle r(n)}$ 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]

Using the Gosper-Petkovšek representation one can transform the original recurrence equation into a recurrence equation for a polynomial sequence ${\textstyle c(n)}$. The other polynomials ${\textstyle a(n),b(n)}$ can be taken as the monic factors of the first coefficient polynomial ${\textstyle p_{0}(n)}$ resp. the last coefficient polynomial shifted ${\textstyle p_{r}(n-r+1)}$. Then ${\textstyle z}$ has to fulfill a certain algebraic equation. Taking all the possible finitely many triples ${\textstyle (a(n),b(n),z)}$ and computing the corresponding polynomial solution of the transformed recurrence equation ${\textstyle c(n)}$ gives a hypergeometric solution if one exists.[1][3][4]

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

algorithm petkovsek is
    input: Linear recurrence equation ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=0,p_{k}\in \mathbb {K} [n],p_{0},p_{r}\neq 0}$.
    output: A hypergeometric solution ${\textstyle y}$ if there are any hypergeometric solutions.

    for each monic divisor ${\textstyle a(n)}$ of ${\textstyle p_{0}(n)}$ do
        for each monic divisor ${\textstyle b(n)}$ of ${\textstyle p_{r}(n-r+1)}$ do
            for each ${\textstyle k=0,\dots ,r}$ do
                ${\textstyle {\tilde {p}}_{k}(n)=p_{k}(n)\prod _{j=0}^{k-1}a(n+j)\prod _{i=k}^{r-1}b(n+i)}$
        ${\textstyle d=\max _{k=0,\dots ,r}\deg({\tilde {p}}_{k}(n))}$
        for each root ${\textstyle z}$ of ${\textstyle \sum _{k=0}^{r}{\text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}}$ do
            Find non-zero polynomial solution ${\textstyle c(n)}$ of ${\textstyle \sum _{k=0}^{r}z^{k}\,{\tilde {p}}_{k}(n)\,c(n+k)=0}$
            if such a non-zero solution ${\textstyle c(n)}$ exists then
                ${\textstyle r(n)=z\,a(n)/b(n)\,c(n+1)/c(n)}$
                return a non-zero solution ${\textstyle y(n)}$ of ${\textstyle y(n+1)=r(n)\,y(n)}$

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]