Petkovšek's algorithm

Petkovšek's algorithm 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 is implemented in all the major computer algebra systems.

Examples

• Given the linear recurrence

$4(n+2)(2n+3)(2n+5)a(n+2) -12(2n+3)(9n^2+27n+22)a(n+1) +81(n+1)( 3n+2)(3n+4) a(n) =0,$

the algorithm finds two linearly independent hypergeometric terms that are solution:

${\frac {\Gamma \left( n+1 \right) }{\Gamma \left( n+3/2 \right) } \left( {\frac {27}{4}} \right) ^{n}},\qquad{\frac {\Gamma \left( n+2/3 \right) \Gamma \left( n+4/3 \right) }{\Gamma \left( n+3/2 \right) \Gamma \left( n+1 \right) } \left( {\frac {27}{4}} \right) ^{n}}.$

(Here, $\Gamma$ denotes Euler's Gamma function.) Note that the second solution is also a binomial coefficient Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): \binom{3n+1}{n} , but it is not the aim of this algorithm to produce binomial expressions.

• Given the sum

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): 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 $\zeta(3)$, Zeilberger's algorithm computes the linear recurrence

$(n+2)^3a(n+2)-(17n^2+51n+39)(2n+3)a(n+1)+(n+1)^3a(n)=0.$

Given this recurrence, the algorithm does not return any hypergeometric solution, which proves that $a(n)$ does not simplify to a hypergeometric term.