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.
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 be a field of characteristic zero and a recurrence equation of order with polynomial coefficients, polynomial right-hand side and unknown polynomial sequence. Furthermore denotes the degree of a polynomial and denotes the leading coefficient of the polynomial. Moreover letfor where denotes the falling factorial and the set of nonegative integers. Then. This is called a degree bound for the polynomial solution. 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 of that degree with arbitrary coefficients in is made and plugged into the recurrence equation. Then the different powers are compared and a system of linear equations for the coefficients of 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.
output: The general polynomial solution if there are any solutions, otherwise false.
for do

repeat




with unknown coefficients for
Compare coefficients of polynomials and to get possible values for
if there are possible values for then
return general solution
else
return false
end if

Example

Applying the formula for the degree bound on the recurrence equationover yields. Hence one can use an ansatz with a quadratic polynomial with. Plugging this ansatz into the original recurrence equation leads toThis is equivalent to the following system of linear equationswith the solution. Therefore the only polynomial solution is.