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)^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.

References

• Burchnall, J. L. (1942). "Differential equations associated with Hypergeometric Functions". Quart. J. Math. 13. pp. 90–106. doi:10.1093/qmath/os-13.1.90. MR 0007820.
• Zeilberger, Doron (1991). "The method of creative telescoping". J. Symb. Comp. 11 (3). pp. 195–204. doi:10.1016/S0747-7171(08)80044-2.
• Petkovsek, Marco (1992). "Hypergeometric solutions of linear recurrences with polynomial coefficients". J. Symb. Comput 14 (2-3). pp. 243––264. doi:10.1016/0747-7171(92)90038-6. MR 1187234.
• Petkovsek, Marko; Wilf, Herbert; Zeilberger, Doron (1996). "A = B".
• Cluzeau, Thomas; van Hoeij, Mark (2006). "Computing hypergeometric solutions of linear recurrence equations". Appl. Alg. Engin. Commun. Comp. 17 (2). pp. 83–115. doi:10.1007/s00200-005-0192-x. MR 2233774.
• Zeilberger, Doron (2006). "A fast algorithm for proving terminating hypergeometric identities". Discr. Math. 306 (10-11). pp. 1072–1075. doi:10.1016/j.disc.2006.03.026.
• Zarzo, A.; Yanez, R. J.; Dehesa, J. S. (2007). "General recurrence and ladder relations of hypergeometric-type functions". J. Comput. Appl. Math. 207 (2). pp. 166–179. doi:10.1016/j.cam.2006.10.012.
• Apagodu, Moa; Zeilberger, Doron (2008). "Searching for strange hypergeometric identities by sheer brute force". INTEGERS: El. J. Combin. Numb. Theory 8. pp. A38.