Polynomial solutions of P-recursive equations

Let \mathbb{K} be a field of characteristic zero and \sum_{k=0}^r p_k(n) \, y (n+k) = f(n) a recurrence equation of order r with polynomial coefficients p_k \in \mathbb{K} [n], polynomial right-hand side f \in \mathbb{K}[n] and unknown polynomial sequence y(n) \in \mathbb{K}[n]. Furthermore \deg (p) denotes the degree of a polynomial p \in \mathbb{K}[n] (with \deg (0) = - \infty for the zero polynomial) and \text{lc}(p) denotes the leading coefficient of the polynomial. Moreover let\begin{align} q_i &= \sum_{k=i}^r \binom{k}{i} p_k, & b &= \max_{i=0,\dots,r}(\deg (q_i)-i), \\ \alpha(n) &= \sum_{i=0,\dots,r \atop \deg (q_i) - i = b} \text{lc} (q_i) n^{\underline{i}}, & d_\alpha &= \max \{n \in \N \, : \, \alpha(n) = 0 \} \cup \{ - \infty\} \end{align}for i=0,\dots,r where n^{\underline{i}} = n (n-1) \cdots (n-i+1) denotes the falling factorial and \N the set of nonnegative integers. Then \deg (y) \leq \max \{ \deg(f) - b, -b-1, d_\alpha \}. This is called a degree bound for the polynomial solution y. 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 y of that degree with arbitrary coefficients in \mathbb{K} is made and plugged into the recurrence equation. Then the different powers are compared and a system of linear equations for the coefficients of y 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 \sum_{k=0}^r p_k(n) \, y (n+k) = f(n), p_k, f \in \mathbb{K}[n], p_0, p_r \neq 0. output: The general polynomial solution y if there are any solutions, otherwise false. for i=0,\dots,r do q_i = \sum_{k=i}^r \binom{k}{i} p_k repeat b=\max_{i=0,\dots,r} (\deg (q_i) - i) \alpha(n) = \sum_{i=0,\dots,r \atop \deg (q_i) - i = b} \text{lc} (q_i) n^{\underline{i}} d_\alpha = \max \{n \in \N \, : \, \alpha(n) = 0 \} \cup \{ - \infty\} d = \max \{ \deg (f) - b, -b-1, d_\alpha\} y(n) = \sum_{j=0}^d y_j n^j with unknown coefficients y_j \in \mathbb{K} for j=0,\dots,d Compare coefficients of polynomials \sum_{k=0}^r p_k(n) \, y (n+k) and f(n) to get possible values for y_j, j=0,\dots,d if there are possible values for y_j then return general solution y else return false end if == Example ==

Applying the formula for the degree bound on the recurrence equation(n^2-2) \, y (n) + (-n^2+2n) \, y (n+1)=2n,over \Q yields \deg (y) \leq 2. Hence one can use an ansatz with a quadratic polynomial y(n) =y_2 n^2 + y_1 n + y_0 with y_0, y_1, y_2 \in \Q. Plugging this ansatz into the original recurrence equation leads to2n = (n^2-2) \, y(n) + (-n^2+2n) \, y (n+1) = (y_1 + y_2) \, n^2 + (2 y_0 + 2 y_2 ) \, n - 2 y_0.This is equivalent to the following system of linear equations\begin{align} \begin{pmatrix} 0 & 1 & 1 \\ 2 & 0 & 2 \\ -2 & 0 & 0 \end{pmatrix} \begin{pmatrix} y_0 \\ y_1 \\ y_2 \end{pmatrix} = \begin{pmatrix} 0 \\ 2 \\ 0 \end{pmatrix} \end{align}with the solution y_0 = 0, y_1 = -1, y_2 = 1. Therefore the only polynomial solution is y (n) = n^2-n. == References ==