Polynomial solutions of P-recursive equations

In mathematics a P-recursive equation can be solved for polynomial solutions. Sergei A. Abramov in 1989 and Marko Petkovšek in 1992 described an algorithm which finds all polynomial solutions of those recurrence equations with polynomial coefficients. The algorithm computes a "degree bound" for the solution in a first step. In a second step an ansatz for a polynomial of this degree is used and the unknown coefficients are computed by a system of linear equations. This article describes this algorithm.
In 1995 Abramov, Bronstein and Petkovšek showed that the polynomial case can be solved more efficiently by considering power series solution of the recurrence equation in a specific power basis (i.e. not the ordinary basis formula_1).
Other algorithms which compute rational or hypergeometric solutions of a linear recurrence equation with polynomial coefficients also use algorithms which compute polynomial solutions.
Degree bound.
Let formula_2 be a field of characteristic zero and formula_3 a recurrence equation of order formula_4 with polynomial coefficients formula_5, polynomial right-hand side formula_6 and unknown polynomial sequence formula_7. Furthermore formula_8 denotes the degree of a polynomial formula_9 (with formula_10 for the zero polynomial) and formula_11 denotes the leading coefficient of the polynomial. Moreover letformula_12for formula_13 where formula_14 denotes the falling factorial and formula_15 the set of nonegative integers. Then formula_16. This is called a degree bound for the polynomial solution formula_17. This bound was shown by Abramov and Petkovšek.
Algorithm.
The algorithm consists of two steps. In a first step the "degree bound" is computed. In a second step an "ansatz" with a polynomial formula_17 of that degree with arbitrary coefficients in formula_2 is made and plugged into the recurrence equation. Then the different powers are compared and a system of linear equations for the coefficients of formula_17 is set up and solved. This is called the "method undetermined coefficients". The algorithm returns the general polynomial solution of a recurrence equation.
 algorithm polynomial_solutions is
 input: Linear recurrence equation formula_21.
 output: The general polynomial solution formula_17 if there are any solutions, otherwise false.
 for formula_13 do
 formula_24
 repeat
 formula_25
 formula_26
 formula_27
 formula_28
 formula_29 with unknown coefficients formula_30 for formula_31
 Compare coefficients of polynomials formula_32 and formula_33 to get possible values for formula_34
 if there are possible values for formula_35 then
 return general solution formula_17
 else
 return false
 end if
Example.
Applying the formula for the degree bound on the recurrence equationformula_37over formula_38 yields formula_39. Hence one can use an ansatz with a quadratic polynomial formula_40 with formula_41. Plugging this ansatz into the original recurrence equation leads toformula_42This is equivalent to the following system of linear equationsformula_43with the solution formula_44. Therefore the only polynomial solution is formula_45.