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.
Given the linear recurrence 4 ( n + 2 ) ( 2 n + 3 ) ( 2 n + 5 ) a ( n + 2 ) − 12 ( 2 n + 3 ) ( 9 n 2 + 27 n + 22 ) a ( n + 1 ) + 81 ( n + 1 ) ( 3 n + 2 ) ( 3 n + 4 ) a ( n ) = 0 , the algorithm finds two linearly independent hypergeometric terms that are solution:
Γ ( n + 1 ) Γ ( n + 3 / 2 ) ( 27 4 ) n , Γ ( n + 2 / 3 ) Γ ( n + 4 / 3 ) Γ ( n + 3 / 2 ) Γ ( n + 1 ) ( 27 4 ) n . (Here, Γ denotes Euler's Gamma function.) Note that the second solution is also a binomial coefficient ( 3 n + 1 n ) , but it is not the aim of this algorithm to produce binomial expressions.
Given the sum a ( n ) = ∑ k = 0 n ( n k ) 2 ( n + k k ) 2 , coming from Apéry's proof of the irrationality of ζ ( 3 ) , Zeilberger's algorithm computes the linear recurrence
( n + 2 ) 3 a ( n + 2 ) − ( 17 n 2 + 51 n + 39 ) ( 2 n + 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.
