P-recursive equation explained

In mathematics a P-recursive equation is a linear equation of sequences where the coefficient sequences can be represented as polynomials. P-recursive equations are linear recurrence equations (or linear recurrence relations or linear difference equations) with polynomial coefficients. These equations play an important role in different areas of mathematics, specifically in combinatorics. The sequences which are solutions of these equations are called holonomic, P-recursive or D-finite.

From the late 1980s, the first algorithms were developed to find solutions for these equations. Sergei A. Abramov, Marko Petkovšek and Mark van Hoeij described algorithms to find polynomial, rational, hypergeometric and d'Alembertian solutions.

Definition

Let $\backslash mathbb$ be a field of characteristic zero (for example $\backslash mathbb\; =\; \backslash mathbb$), $p\_k(n)\; \backslash in\; \backslash mathbb\; [n]$ polynomials for $k\; =\; 0,\backslash dots,r$,$f\; \backslash in\; \backslash mathbb^$ a sequence and $y\; \backslash in\; \backslash mathbb^$ an unknown sequence. The equation$$\backslash sum\_^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\_^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)$.

Closed form solutions

Let $\backslash sum\_^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$. As a subspace of the space of sequences this kernel has a basis.^[1] Let $\backslash$ be a basis of $\backslash ker\; L$, then the formal sum $c\_1\; y^\; +\; \backslash dots\; +\; c\_m\; y^$ for arbitrary constants $c\_1,\backslash dots,c\_m\; \backslash in\; \backslash mathbb$ is called the general solution of the homogeneous problem $Ly=0$. If $\backslash tilde$ is a particular solution of $Ly=f$, i.e. $L\; \backslash tilde=f$, then $c\_1\; y^\; +\; \backslash dots\; +\; c\_m\; y^\; +\; \backslash tilde$ is also a solution of the inhomogeneous problem and it is called the general solution of the inhomogeneous problem.

Polynomial solutions

See main article: 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\; [n]$, with a polynomial right-hand side$f(n)\; \backslash in\; \backslash mathbb\; [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.^{[2] [3] [4]} 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)\_$).^[5]

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

Rational solutions

See main article: Abramov's algorithm. In 1989 Sergei A. Abramov showed that a general rational solution, i.e. $y(n)\; \backslash in\; \backslash mathbb\; (n)$, with polynomial right-hand side $f(n)\; \backslash in\; \backslash mathbb[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

all rational solutions can be found by computing all polynomial solutions of a transformed equation.^[6]

Hypergeometric solution

See main article: Petkovšek's algorithm. A sequence $y(n)$ is called hypergeometric if the ratio of two consecutive terms is a rational function in

, i.e. $y\; (n+1)\; /\; y(n)\; \backslash in\; \backslash mathbb\; (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

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)^\; \backslash Gamma(n-\backslash xi\_2)^\; \backslash cdots\; \backslash Gamma(n-\backslash xi\_s)^$$for some $c\; \backslash in\; \backslash mathbb,\; z\; \backslash in\; \backslash overline,\; s\; \backslash in\; \backslash N,\; r(n)\; \backslash in\; \backslash overline\backslash mathbb(n),\; \backslash xi\_1,\; \backslash dots,\; \backslash xi\_s\; \backslash in\; \backslash overline$ 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$ the algebraic closure of the field $\backslash mathbb$. 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.^{[7] [8]}

D'Alembertian solutions

A sequence

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.^[9]

Examples

Signed permutation matrices

The number of signed permutation matrices of size

can be described by the sequence $y(n)\; \backslash in\; \backslash Q^$. 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.^[10]

Involutions

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.

Applications

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(n,k)$ where $\backslash mathbb(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$.

References

1. 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.
2. 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.
3. 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.
4. Book: A=B. Petkovšek. Marko. Wilf. Herbert S.. Zeilberger. Doron. 1996. A K Peters. 978-1568810638. 33898705.
5. 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 .
6. Abramov. Sergei A.. 1989. Rational solutions of linear differential and difference equations with polynomial coefficients. USSR Computational Mathematics and Mathematical Physics. 29. 6. 7–12. 10.1016/s0041-5553(89)80002-3. 0041-5553.
7. van Hoeij. Mark. 1999. Finite singularities and hypergeometric solutions of linear recurrence equations. Journal of Pure and Applied Algebra. 139. 1–3. 109–131. 10.1016/s0022-4049(99)00008-0. 0022-4049.
8. Cluzeau. Thomas. van Hoeij. Mark. 2006. Computing Hypergeometric Solutions of Linear Recurrence Equations. Applicable Algebra in Engineering, Communication and Computing. en. 17. 2. 83–115. 10.1007/s00200-005-0192-x. 7496623 . 0938-1279.
9. Book: Abramov. Sergei A.. Petkovšek. Marko. Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94 . D'Alembertian solutions of linear differential and difference equations . 1994. ACM. 169–174. 10.1145/190347.190412. 978-0897916387. 2802734 .
10. Web site: A000165 - OEIS. oeis.org. 2018-07-02.