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

Let ${\textstyle \mathbb {K} }${\textstyle \mathbb {K} } be a field of characteristic zero. A nonzero sequence ${\textstyle y(n)}${\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)}${\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]}${\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]}${\textstyle a,b,c\in \mathbb {K} [n]} and ${\textstyle 0\neq z\in \mathbb {K} }${\textstyle 0\neq z\in \mathbb {K} } such that

${\displaystyle r(n)=z{\frac {a(n)}{b(n)}}{\frac {c(n+1)}{c(n)}}}${\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}${\textstyle \gcd(a(n),b(n+k))=1} for every nonnegative integer ${\textstyle k\in \mathbb {N} }${\textstyle k\in \mathbb {N} },
2. ${\textstyle \gcd(a(n),c(n))=1}${\textstyle \gcd(a(n),c(n))=1} and
3. ${\textstyle \gcd(b(n),c(n+1))=1}${\textstyle \gcd(b(n),c(n+1))=1}.

This representation of ${\textstyle r(n)}${\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)}${\textstyle c(n)}. The other polynomials ${\textstyle a(n),b(n)}${\textstyle a(n),b(n)} can be taken as the monic factors of the first coefficient polynomial ${\textstyle p_{0}(n)}${\textstyle p_{0}(n)} resp. the last coefficient polynomial shifted ${\textstyle p_{r}(n-r+1)}${\textstyle p_{r}(n-r+1)}. Then ${\textstyle z}${\textstyle z} has to fulfill a certain algebraic equation. Taking all the possible finitely many triples ${\textstyle (a(n),b(n),z)}${\textstyle (a(n),b(n),z)} and computing the corresponding polynomial solution of the transformed recurrence equation ${\textstyle c(n)}${\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]}${\textstyle p(n)\in \mathbb {K} [n]} is denoted by ${\textstyle \deg(p(n))}${\textstyle \deg(p(n))} and the coefficient of ${\textstyle n^{d}}${\textstyle n^{d}} is denoted by ${\textstyle {\text{coeff}}(p(n),n^{d})}${\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}${\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}${\textstyle y} if there are any hypergeometric solutions.
 for each monic divisor ${\textstyle a(n)}${\textstyle a(n)} of ${\textstyle p_{0}(n)}${\textstyle p_{0}(n)} do
 for each monic divisor ${\textstyle b(n)}${\textstyle b(n)} of ${\textstyle p_{r}(n-r+1)}${\textstyle p_{r}(n-r+1)} do
 for each ${\textstyle k=0,\dots ,r}${\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 {\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))}${\textstyle d=\max _{k=0,\dots ,r}\deg({\tilde {p}}_{k}(n))}
 for each root ${\textstyle z}${\textstyle z} of ${\textstyle \sum _{k=0}^{r}{\text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}}${\textstyle \sum _{k=0}^{r}{\text{coeff}}({\tilde {p}}_{k}(n),n^{d})z^{k}} do
 Find non-zero polynomial solution ${\textstyle c(n)}${\textstyle c(n)} of ${\textstyle \sum _{k=0}^{r}z^{k},円{\tilde {p}}_{k}(n),円c(n+k)=0}${\textstyle \sum _{k=0}^{r}z^{k},円{\tilde {p}}_{k}(n),円c(n+k)=0}
 if such a non-zero solution ${\textstyle c(n)}${\textstyle c(n)} exists then
 ${\textstyle r(n)=z,円a(n)/b(n),円c(n+1)/c(n)}${\textstyle r(n)=z,円a(n)/b(n),円c(n+1)/c(n)}
 return a non-zero solution ${\textstyle y(n)}${\textstyle y(n)} of ${\textstyle y(n+1)=r(n),円y(n)}${\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]

The number of signed permutation matrices of size ${\textstyle n\times n}${\textstyle n\times n} can be described by the sequence ${\textstyle y(n)}${\textstyle y(n)} which is determined by the recurrence equation$${\displaystyle 4(n+1)^{2},円y(n)+2,円y(n+1)+(-1),円y(n+2)=0}$${\displaystyle 4(n+1)^{2},円y(n)+2,円y(n+1)+(-1),円y(n+2)=0}over ${\textstyle \mathbb {Q} }${\textstyle \mathbb {Q} }. Taking ${\textstyle a(n)=n+1,b(n)=1}${\textstyle a(n)=n+1,b(n)=1} as monic divisors of ${\textstyle p_{0}(n)=4(n+1)^{2},p_{2}(n)=-1}${\textstyle p_{0}(n)=4(n+1)^{2},p_{2}(n)=-1} respectively, one gets ${\textstyle z=\pm 2}${\textstyle z=\pm 2}. For ${\textstyle z=2}${\textstyle z=2} the corresponding recurrence equation which is solved in Petkovšek's algorithm is$${\displaystyle 4(n+1)^{2},円c(n)+4(n+1),円c(n+1)-4(n+1)(n+2),円c(n+2)=0.}$${\displaystyle 4(n+1)^{2},円c(n)+4(n+1),円c(n+1)-4(n+1)(n+2),円c(n+2)=0.}This recurrence equation has the polynomial solution ${\textstyle c(n)=c_{0}}${\textstyle c(n)=c_{0}} for an arbitrary ${\textstyle c_{0}\in \mathbb {Q} }${\textstyle c_{0}\in \mathbb {Q} }. Hence ${\textstyle r(n)=2(n+1)}${\textstyle r(n)=2(n+1)} and ${\textstyle y(n)=2^{n},円n!}${\textstyle y(n)=2^{n},円n!} 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]

Given the sum

${\displaystyle a(n)=\sum _{k=0}^{n}{{\binom {n}{k}}^{2}{\binom {n+k}{k}}^{2}},}${\displaystyle a(n)=\sum _{k=0}^{n}{{\binom {n}{k}}^{2}{\binom {n+k}{k}}^{2}},}

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

${\displaystyle (n+2)^{3},円a(n+2)-(17n^{2}+51n+39)(2n+3),円a(n+1)+(n+1)^{3},円a(n)=0.}${\displaystyle (n+2)^{3},円a(n+2)-(17n^{2}+51n+39)(2n+3),円a(n+1)+(n+1)^{3},円a(n)=0.}

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

• Combinatorics