Polynomial solutions of P-recursive equations

In mathematics a <a href="/facts/P-recursive_equation/U03dgoPw">P-recursive equation</a> can be solved for polynomial solutions. Sergei A. Abramov in 1989 and <a href="/facts/Marko_Petkov%25C5%25A1ek/xSEcWwv1">Marko Petkovšek</a> in 1992 described an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> which finds all <a href="/facts/Polynomial_ring/ua3vk8Ih">polynomial</a> 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 <a href="/facts/Ansatz/3epoB3Rg">ansatz</a> for a polynomial of this degree is used and the unknown coefficients are computed by a <a href="/facts/System_of_linear_equations/fk9CFdgp">system of linear equations</a>. This article describes this algorithm.
In 1995 Abramov, Bronstein and Petkovšek showed that the polynomial case can be solved more efficiently by considering <a href="/facts/Formal_power_series/CNmaG0Vk">power series</a> solution of the recurrence equation in a specific power basis (i.e. not the ordinary basis 
 
 
 
 (
 
 x
 
 n
 
 
 
 )
 
 n
 ∈
 
 N
 
 
 
 
 
 {\textstyle (x^{n})_{n\in \mathbb {N} }}
 
).
Other algorithms which compute <a href="/facts/Abramov%2527s_algorithm/F3B9IA3N">rational</a> or <a href="/facts/Petkov%25C5%25A1ek%2527s_algorithm/rlS9wb3m">hypergeometric</a> solutions of a linear recurrence equation with polynomial coefficients also use algorithms which compute polynomial solutions.

Polynomial solutions of P-recursive equations open-in-new

Polynomial solutions of P-recursive equations