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 K {\textstyle \mathbb {K} } be a field of characteristic zero. A nonzero sequence y ( n ) {\textstyle y(n)} is called hypergeometric if the ratio of two consecutive terms is rational, i.e. y ( n + 1 ) / y ( n ) ∈ 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 r ( n ) ∈ K [ n ] {\textstyle r(n)\in \mathbb {K} [n]} be a nonzero rational function. Then there exist monic polynomials a , b , c ∈ K [ n ] {\textstyle a,b,c\in \mathbb {K} [n]} and 0 ≠ z ∈ K {\textstyle 0\neq z\in \mathbb {K} } such that
r ( n ) = z a ( n ) b ( n ) c ( n + 1 ) c ( n ) {\displaystyle r(n)=z{\frac {a(n)}{b(n)}}{\frac {c(n+1)}{c(n)}}}
and
gcd ( a ( n ) , b ( n + k ) ) = 1 {\textstyle \gcd(a(n),b(n+k))=1} for every nonnegative integer k ∈ N {\textstyle k\in \mathbb {N} } ,
gcd ( a ( n ) , c ( n ) ) = 1 {\textstyle \gcd(a(n),c(n))=1} and
gcd ( b ( n ) , c ( n + 1 ) ) = 1 {\textstyle \gcd(b(n),c(n+1))=1} . This representation of 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. 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 c ( n ) {\textstyle c(n)} . The other polynomials a ( n ) , b ( n ) {\textstyle a(n),b(n)} can be taken as the monic factors of the first coefficient polynomial p 0 ( n ) {\textstyle p_{0}(n)} resp. the last coefficient polynomial shifted p r ( n − r + 1 ) {\textstyle p_{r}(n-r+1)} . Then z {\textstyle z} has to fulfill a certain algebraic equation. Taking all the possible finitely many triples ( a ( n ) , b ( n ) , z ) {\textstyle (a(n),b(n),z)} and computing the corresponding polynomial solution of the transformed recurrence equation c ( n ) {\textstyle c(n)} gives a hypergeometric solution if one exists. In the following pseudocode the degree of a polynomial p ( n ) ∈ K [ n ] {\textstyle p(n)\in \mathbb {K} [n]} is denoted by deg ( p ( n ) ) {\textstyle \deg(p(n))} and the coefficient of n d {\textstyle n^{d}} is denoted by coeff ( p ( n ) , n d ) {\textstyle {\text{coeff}}(p(n),n^{d})} .
… excerpt ends here. Continue reading the full article.
