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 ${\binom {3n+1}{n}}$, but it is not the aim of this algorithm to produce binomial expressions.

• Given the sum

$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)^{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 $a(n)$ does not simplify to a hypergeometric term.

See also

Marko Petkovšek

References

• Template:Cite article
• Template:Cite article
• Template:Cite article
• Petkovšek, Marko; Wilf, Herbert; Zeilberger, Doron (1996). "A = B".
• Template:Cite article
• Template:Cite article
• Template:Cite article
• Template:Cite article