# 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
${\displaystyle 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:

${\displaystyle {{\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, ${\displaystyle \Gamma }$ denotes Euler's Gamma function.) Note that the second solution is also a binomial coefficient ${\displaystyle {\binom {3n+1}{n}}}$, but it is not the aim of this algorithm to produce binomial expressions.

• Given the sum
${\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)}$, 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.}$

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