Polynomial solutions of P-recursive equations

Let ${\textstyle \mathbb {K} }$ be a field of characteristic zero and ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ a recurrence equation of order ${\textstyle r}$ with polynomial coefficients ${\textstyle p_{k}\in \mathbb {K} [n]}$, polynomial right-hand side ${\textstyle f\in \mathbb {K} [n]}$ and unknown polynomial sequence ${\displaystyle y(n)\in \mathbb {K} [n]}$. Furthermore ${\textstyle \deg(p)}$ denotes the degree of a polynomial ${\textstyle p\in \mathbb {K} [n]}$ (with ${\textstyle \deg(0)=-\infty }$ for the zero polynomial) and ${\textstyle {\text{lc}}(p)}$ denotes the leading coefficient of the polynomial. Moreover let

$${\displaystyle {\begin{aligned}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 \mathbb {N} \,:\,\alpha (n)=0\}\cup \{-\infty \}\end{aligned}}}$$

for ${\textstyle i=0,\dots ,r}$ where ${\textstyle n^{\underline {i}}=n(n-1)\cdots (n-i+1)}$ denotes the falling factorial and ${\textstyle \mathbb {N} }$ the set of nonnegative integers. Then ${\textstyle \deg(y)\leq \max\{\deg(f)-b,-b-1,d_{\alpha }\}}$. This is called a degree bound for the polynomial solution ${\textstyle y}$. This bound was shown by Abramov and Petkovšek.[1][2][3][4]

The algorithm consists of two steps. In a first step the degree bound is computed. In a second step an ansatz with a polynomial ${\textstyle y}$ of that degree with arbitrary coefficients in ${\textstyle \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 ${\textstyle y}$ is set up and solved. This is called the method undetermined coefficients.[5] The algorithm returns the general polynomial solution of a recurrence equation.

algorithm polynomial_solutions is
    input: Linear recurrence equation ${\textstyle \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 ${\textstyle y}$ if there are any solutions, otherwise false.

    for ${\textstyle i=0,\dots ,r}$ do
        ${\textstyle q_{i}=\sum _{k=i}^{r}{\binom {k}{i}}p_{k}}$
    repeat
    ${\textstyle b=\max _{i=0,\dots ,r}(\deg(q_{i})-i)}$
    ${\textstyle \alpha (n)=\sum _{i=0,\dots ,r \atop \deg(q_{i})-i=b}{\text{lc}}(q_{i})n^{\underline {i}}}$
    ${\textstyle d_{\alpha }=\max\{n\in \mathbb {N} \,:\,\alpha (n)=0\}\cup \{-\infty \}}$
    ${\textstyle d=\max\{\deg(f)-b,-b-1,d_{\alpha }\}}$
    ${\textstyle y(n)=\sum _{j=0}^{d}y_{j}n^{j}}$ with unknown coefficients ${\textstyle y_{j}\in \mathbb {K} }$ for ${\textstyle j=0,\dots ,d}$
    Compare coefficients of polynomials ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)}$ and ${\textstyle f(n)}$ to get possible values for ${\textstyle y_{j},j=0,\dots ,d}$
    if there are possible values for ${\textstyle y_{j}}$ then
        return general solution ${\textstyle y}$
    else
        return false
    end if

Applying the formula for the degree bound on the recurrence equation

$${\displaystyle (n^{2}-2)\,y(n)+(-n^{2}+2n)\,y(n+1)=2n,}$$

over ${\textstyle \mathbb {Q} }$ yields ${\textstyle \deg(y)\leq 2}$. Hence one can use an ansatz with a quadratic polynomial ${\textstyle y(n)=y_{2}n^{2}+y_{1}n+y_{0}}$ with ${\textstyle y_{0},y_{1},y_{2}\in \mathbb {Q} }$. Plugging this ansatz into the original recurrence equation leads to

$${\displaystyle 2n=(n^{2}-2)\,y(n)+(-n^{2}+2n)\,y(n+1)=(y_{1}+y_{2})\,n^{2}+(2y_{0}+2y_{2})\,n-2y_{0}.}$$

This is equivalent to the following system of linear equations

$${\displaystyle {\begin{aligned}{\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{aligned}}}$$

with the solution ${\textstyle y_{0}=0,y_{1}=-1,y_{2}=1}$. Therefore the only polynomial solution is ${\textstyle y(n)=n^{2}-n}$.