Polynomial solutions of P-recursive equations explained

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.^{[1] [2]} 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 $(x^n)\_$).^[3]

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 $\backslash mathbb$ be a field of characteristic zero and $\backslash sum\_^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n)$ a recurrence equation of order $r$ with polynomial coefficients $p\_k\; \backslash in\; \backslash mathbb\; [n]$, polynomial right-hand side $f\; \backslash in\; \backslash mathbb[n]$ and unknown polynomial sequence

y(n) \in K [n] . Furthermore $\backslash deg\; (p)$ denotes the degree of a polynomial $p\; \backslash in\; \backslash mathbb[n]$ (with $\backslash deg\; (0)\; =\; -\; \backslash infty$ for the zero polynomial) and $\backslash text(p)$ denotes the leading coefficient of the polynomial. Moreover letfor $i=0,\backslash dots,r$ where $n^\; =\; n\; (n-1)\; \backslash cdots\; (n-i+1)$ denotes the falling factorial and $\backslash N$ the set of nonnegative integers. Then $\backslash deg\; (y)\; \backslash leq\; \backslash max\; \backslash$. This is called a degree bound for the polynomial solution $y$. This bound was shown by Abramov and Petkovšek.^[4]

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 $\backslash mathbb$ 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.^[5] The algorithm returns the general polynomial solution of a recurrence equation. algorithm polynomial_solutions is input: Linear recurrence equation $\backslash sum\_^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n),\; p\_k,\; f\; \backslash in\; \backslash mathbb[n],\; p\_0,\; p\_r\; \backslash neq\; 0$. output: The general polynomial solution $y$ if there are any solutions, otherwise false. for $i=0,\backslash dots,r$ do $q\_i\; =\; \backslash sum\_^r\; \backslash binom\; p\_k$ repeat $b=\backslash max\_\; (\backslash deg\; (q\_i)\; -\; i)$ $\backslash alpha(n)\; =\; \backslash sum\_\; \backslash text\; (q\_i)\; n^$ $d\_\backslash alpha\; =\; \backslash max\; \backslash \; \backslash cup\; \backslash$ $d\; =\; \backslash max\; \backslash$ $y(n)\; =\; \backslash sum\_^d\; y\_j\; n^j$ with unknown coefficients $y\_j\; \backslash in\; \backslash mathbb$ for $j=0,\backslash dots,d$ Compare coefficients of polynomials $\backslash sum\_^r\; p\_k(n)\; \backslash ,\; y\; (n+k)$ and $f(n)$ to get possible values for $y\_j,\; j=0,\backslash 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)\; \backslash ,\; y\; (n)\; +\; (-n^2+2n)\; \backslash ,\; y\; (n+1)=2n,$$over $\backslash Q$ yields $\backslash deg\; (y)\; \backslash 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\; \backslash in\; \backslash Q$. Plugging this ansatz into the original recurrence equation leads to$$2n\; =\; (n^2-2)\; \backslash ,\; y(n)\; +\; (-n^2+2n)\; \backslash ,\; y\; (n+1)\; =\; (y\_1\; +\; y\_2)\; \backslash ,\; n^2\; +\; (2\; y\_0\; +\; 2\; y\_2)\; \backslash ,\; n\; -\; 2\; y\_0.$$This is equivalent to the following system of linear equationswith the solution $y\_0\; =\; 0,\; y\_1\; =\; -1,\; y\_2\; =\; 1$. Therefore the only polynomial solution is $y\; (n)\; =\; n^2-n$.

References

1. Abramov. Sergei A.. 1989. Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations. Moscow University Computational Mathematics and Cybernetics. 3.
2. Petkovšek. Marko. 1992. Hypergeometric solutions of linear recurrences with polynomial coefficients. Journal of Symbolic Computation. 14. 2–3. 243–264. 10.1016/0747-7171(92)90038-6. 0747-7171. free.
3. Book: Abramov. Sergei A.. Bronstein. Manuel. Petkovšek. Marko. Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95 . On polynomial solutions of linear operator equations . 1995. ACM. 290–296. 10.1145/220346.220384. 978-0897916998. 10.1.1.46.9373. 14963237 .
4. Weixlbaumer, Christian (2001). Solutions of difference equations with polynomial coefficients. Diploma Thesis, Johannes Kepler Universität Linz
5. Book: A=B. Petkovšek. Marko. Wilf. Herbert S.. Zeilberger. Doron. 1996. A K Peters. 978-1568810638. 33898705.