P-recursive equation

Let $\backslash mathbb\{K\}$ be a field of characteristic zero (for example $\backslash mathbb\{K\}\; =\; \backslash mathbb\{Q\}$), $p\_k(n)\; \backslash in\; \backslash mathbb\{K\}\; [n]$ polynomials for $k\; =\; 0,\backslash dots,r$,$f\; \backslash in\; \backslash mathbb\{K\}^\{\backslash N\}$ a sequence and $y\; \backslash in\; \backslash mathbb\{K\}^\{\backslash N\}$ an unknown sequence. The equation$$\backslash sum\_\{k=0\}^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n)$$is called a linear recurrence equation with polynomial coefficients (all recurrence equations in this article are of this form). If $p\_0$ and $p\_r$ are both nonzero, then $r$ is called the order of the equation. If $f$ is zero the equation is called homogeneous, otherwise it is called inhomogeneous.

This can also be written as $L\; y\; =\; f$ where $L=\backslash sum\_\{k=0\}^r\; p\_k\; N^k$ is a linear recurrence operator with polynomial coefficients and $N$ is the shift operator, i.e. $N\; \backslash ,\; y\; (n)\; =\; y\; (n+1)$.

Let $\backslash sum\_\{k=0\}^r\; p\_k(n)\; \backslash ,\; y\; (n+k)\; =\; f(n)$ or equivalently $Ly=f$ be a recurrence equation with polynomial coefficients. There exist several algorithms which compute solutions of this equation. These algorithms can compute polynomial, rational, hypergeometric and d'Alembertian solutions. The solution of a homogeneous equation is given by the kernel of the linear recurrence operator: $\backslash ker\; L\; =\; \backslash \{\; y\; \backslash in\; \backslash mathbb\{K\}^\backslash N\; \backslash ,\; :\; \backslash ,\; L\; y\; =\; 0\backslash \}$. As a subspace of the space of sequences this kernel has a basis.If sequences are considered equal if they are equal in almost all terms, then this basis is finite. More on this can be found in the book A=B by Petkovšek, Wilf and Zeilberger. Let $\backslash \{\; y^\{(1)\},\; y^\{(2)\},\; \backslash dots,\; y^\{(m)\}\; \backslash \}$ be a basis of $\backslash ker\; L$, then the formal sum $c\_1\; y^\{(1)\}\; +\; \backslash dots\; +\; c\_m\; y^\{(m)\}$ for arbitrary constants $c\_1,\backslash dots,c\_m\; \backslash in\; \backslash mathbb\{K\}$ is called the general solution of the homogeneous problem $Ly=0$. If $\backslash tilde\{y\}$ is a particular solution of $Ly=f$, i.e. $L\; \backslash tilde\{y\}=f$, then $c\_1\; y^\{(1)\}\; +\; \backslash dots\; +\; c\_m\; y^\{(m)\}\; +\; \backslash tilde\{y\}$ is also a solution of the inhomogeneous problem and it is called the general solution of the inhomogeneous problem.

{{Main|Polynomial solutions of P-recursive equations}}In the late 1980s Sergei A. Abramov described an algorithm which finds the general polynomial solution of a recurrence equation, i.e. $y\; (n)\; \backslash in\; \backslash mathbb\{K\}\; [n]$, with a polynomial right-hand side$f(n)\; \backslash in\; \backslash mathbb\{K\}\; [n]$. He (and a few years later Marko Petkovšek) gave a degree bound for polynomial solutions. This way the problem can simply be solved by considering a system of linear equations.{{Cite journal|last=Abramov|first=Sergei A.|date=1989|title=Problems in computer algebra that are connected with a search for polynomial solutions of linear differential and difference equations|journal=Moscow University Computational Mathematics and Cybernetics|volume=3}}{{Cite journal|last=Petkovšek|first=Marko|date=1992|title=Hypergeometric solutions of linear recurrences with polynomial coefficients|journal=Journal of Symbolic Computation|volume=14|issue=2–3|pages=243–264|doi=10.1016/0747-7171(92)90038-6|issn=0747-7171|doi-access=}}{{Cite book|url=https://www.math.upenn.edu/~wilf/Downld.html|title=A=B|last1=Petkovšek|first1=Marko|last2=Wilf|first2=Herbert S.|last3=Zeilberger|first3=Doron|date=1996|publisher=A K Peters|isbn=978-1568810638|oclc=33898705}} 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)\_\{n\; \backslash in\; \backslash N\}$).{{Cite book|last1=Abramov|first1=Sergei A.|last2=Bronstein|first2=Manuel|last3=Petkovšek|first3=Marko|title=Proceedings of the 1995 international symposium on Symbolic and algebraic computation - ISSAC '95 |chapter=On polynomial solutions of linear operator equations |date=1995|publisher=ACM|pages=290–296|doi=10.1145/220346.220384|isbn=978-0897916998|citeseerx=10.1.1.46.9373|s2cid=14963237 }}

The other algorithms for finding more general solutions (e.g. rational or hypergeometric solutions) also rely on algorithms which compute polynomial solutions.

{{Main|Abramov's algorithm}}In 1989 Sergei A. Abramov showed that a general rational solution, i.e. $y(n)\; \backslash in\; \backslash mathbb\{K\}\; (n)$, with polynomial right-hand side $f(n)\; \backslash in\; \backslash mathbb\{K\}[n]$, can be found by using the notion of a universal denominator. A universal denominator is a polynomial $u$ such that the denominator of every rational solution divides $u$. Abramov showed how this universal denominator can be computed by only using the first and the last coefficient polynomial $p\_0$ and $p\_r$. Substituting this universal denominator for the unknown denominator of $y$ all rational solutions can be found by computing all polynomial solutions of a transformed equation.{{Cite journal|last=Abramov|first=Sergei A.|date=1989|title=Rational solutions of linear differential and difference equations with polynomial coefficients|journal=USSR Computational Mathematics and Mathematical Physics|volume=29|issue=6|pages=7–12|doi=10.1016/s0041-5553(89)80002-3|issn=0041-5553}}

{{Main|Petkovšek's algorithm}}A sequence $y(n)$ is called hypergeometric if the ratio of two consecutive terms is a rational function in $n$, i.e. $y\; (n+1)\; /\; y(n)\; \backslash in\; \backslash mathbb\{K\}\; (n)$. This is the case if and only if the sequence is the solution of a first-order recurrence equation with polynomial coefficients. The set of hypergeometric sequences is not a subspace of the space of sequences as it is not closed under addition.

In 1992 Marko Petkovšek gave an algorithm to get the general hypergeometric solution of a recurrence equation where the right-hand side $f$ is the sum of hypergeometric sequences. The algorithm makes use of the Gosper-Petkovšek normal-form of a rational function. With this specific representation it is again sufficient to consider polynomial solutions of a transformed equation.

A different and more efficient approach is due to Mark van Hoeij. Considering the roots of the first and the last coefficient polynomial $p\_0$ and $p\_r$ – called singularities – one can build a solution step by step making use of the fact that every hypergeometric sequence $y\; (n)$ has a representation of the form$$y\; (n)\; =\; c\; \backslash ,\; r(n)\backslash ,\; z^n\; \backslash ,\; \backslash Gamma(n-\backslash xi\_1)^\{e\_1\}\; \backslash Gamma(n-\backslash xi\_2)^\{e\_2\}\; \backslash cdots\; \backslash Gamma(n-\backslash xi\_s)^\{e\_s\}$$for some $c\; \backslash in\; \backslash mathbb\{K\},\; z\; \backslash in\; \backslash overline\{\backslash mathbb\{K\}\},\; s\; \backslash in\; \backslash N,\; r(n)\; \backslash in\; \backslash overline\backslash mathbb\{K\}(n),\; \backslash xi\_1,\; \backslash dots,\; \backslash xi\_s\; \backslash in\; \backslash overline\{\backslash mathbb\{K\}\}$ with $\backslash xi\_i-\backslash xi\_j\; \backslash notin\; \backslash Z$ for $i\; \backslash neq\; j$ and $e\_1,\; \backslash dots,\; e\_s\; \backslash in\; \backslash Z$. Here $\backslash Gamma\; (n)$ denotes the Gamma function and $\backslash overline\{\backslash mathbb\{K\}\}$ the algebraic closure of the field $\backslash mathbb\{K\}$. Then the $\backslash xi\_1,\; \backslash dots,\; \backslash xi\_s$ have to be singularities of the equation (i.e. roots of $p\_0$ or $p\_r$). Furthermore one can compute bounds for the exponents $e\_i$. For fixed values $\backslash xi\_1,\; \backslash dots,\; \backslash xi\_s,\; e\_1,\; \backslash dots,\; e\_s$ it is possible to make an ansatz which gives candidates for $z$. For a specific $z$ one can again make an ansatz to get the rational function $r(n)$ by Abramov's algorithm. Considering all possibilities one gets the general solution of the recurrence equation.{{Cite journal|last=van Hoeij|first=Mark|date=1999|title=Finite singularities and hypergeometric solutions of linear recurrence equations|journal=Journal of Pure and Applied Algebra|volume=139|issue=1–3|pages=109–131|doi=10.1016/s0022-4049(99)00008-0|issn=0022-4049|doi-access=}}{{Cite journal|last1=Cluzeau|first1=Thomas|last2=van Hoeij|first2=Mark|date=2006|title=Computing Hypergeometric Solutions of Linear Recurrence Equations|journal=Applicable Algebra in Engineering, Communication and Computing|language=en|volume=17|issue=2|pages=83–115|doi=10.1007/s00200-005-0192-x|s2cid=7496623 |issn=0938-1279}}

A sequence $y$ is called d'Alembertian if $y\; =\; h\_1\; \backslash sum\; h\_2\; \backslash sum\; \backslash cdots\; \backslash sum\; h\_k$ for some hypergeometric sequences $h\_1,\backslash dots,h\_k$ and $y=\backslash sum\; x$ means that $\backslash Delta\; y\; =\; x$ where $\backslash Delta$ denotes the difference operator, i.e. $\backslash Delta\; y\; =\; N\; y\; -\; y\; =\; y\; (n+1)\; -\; y(n)$. This is the case if and only if there are first-order linear recurrence operators $L\_1,\; \backslash dots,\; L\_k$ with rational coefficients such that $L\_k\; \backslash cdots\; L\_1\; y\; =\; 0$.

1994 Abramov and Petkovšek described an algorithm which computes the general d'Alembertian solution of a recurrence equation. This algorithm computes hypergeometric solutions and reduces the order of the recurrence equation recursively.{{Cite book|last1=Abramov|first1=Sergei A.|last2=Petkovšek|first2=Marko|title=Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94 |chapter=D'Alembertian solutions of linear differential and difference equations |date=1994|publisher=ACM|pages=169–174|doi=10.1145/190347.190412|isbn=978-0897916387|s2cid=2802734 }}

The number of signed permutation matrices of size $n\; \backslash times\; n$ can be described by the sequence $y(n)\; \backslash in\; \backslash Q^\{\backslash N\}$. A signed permutation matrix is a square matrix which has exactly one nonzero entry in every row and in every column. The nonzero entries can be $\backslash pm\; 1$. The sequence is determined by the linear recurrence equation with polynomial coefficients$$y\; (n)\; =\; 4(n-1)^2\; \backslash ,\; y\; (n-2)\; +\; 2\; \backslash ,\; y\; (n-1)$$and the initial values $y(0)\; =\; 1,\; y(1)\; =\; 2$. Applying an algorithm to find hypergeometric solutions one can find the general hypergeometric solution$$y\; (n)\; =\; c\; \backslash ,\; 2^n\; n!$$for some constant $c$. Also considering the initial values, the sequence $y\; (n)\; =\; 2^n\; n!$ describes the number of signed permutation matrices.{{Cite web|url=https://oeis.org/A000165|title=A000165 - OEIS|website=oeis.org|access-date=2018-07-02}}

The number of involutions $y(n)$ of a set with $n$ elements is given by the recurrence equation$$y\; (n)\; =\; (n-1)\; \backslash ,\; y\; (n-2)\; +\; y\; (n-1).$$Applying for example Petkovšek's algorithm it is possible to see that there is no polynomial, rational or hypergeometric solution for this recurrence equation.

A function $F(n,k)$ is called hypergeometric if $F(n,k+1)/F(n,k),\; F(n+1,k)/F(n,k)\; \backslash in\; \backslash mathbb\{K\}(n,k)$ where $\backslash mathbb\{K\}(n,k)$ denotes the rational functions in $n$ and $k$. A hypergeometric sum is a finite sum of the form $f(n)=\backslash sum\_k\; F(n,k)$ where $F(n,k)$ is hypergeometric. Zeilberger's creative telescoping algorithm can transform such a hypergeometric sum into a recurrence equation with polynomial coefficients. This equation can then be solved to get for example a linear combination of hypergeometric solutions which is called a closed form solution of $f$.

Category:Polynomials