# P-recursive equation Information

*https://en.wikipedia.org/wiki/P-recursive_equation*

This article needs attention from an expert in mathematics. The specific problem is: to review the article. (October 2019) |

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 on 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 be a field of characteristic zero (for example ), polynomials for , a sequence and an unknown sequence. The equation

This can also be written as where is a linear recurrence operator with polynomial coefficients and is the shift operator, i.e. .

## Closed form solutions

Let or equivalently 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: . As a subspace of the space of sequences this kernel has a
basis.^{
[1]} Let be a basis of , then the formal sum for arbitrary constants is called the general solution of the homogeneous problem . If is a particular solution of , i.e. , then is also a solution of the inhomogeneous problem and it is called the general solution of the inhomogeneous problem.

### Polynomial solutions

In the late 1980s Sergei A. Abramov described an algorithm which finds the general polynomial solution of a recurrence equation, i.e. , with a polynomial right-hand side. 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 ).^{
[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

In 1989 Sergei A. Abramov showed that a general
rational solution, i.e. , with polynomial right-hand side , can be found by using the notion of a universal denominator. A universal denominator is a polynomial such that the denominator of every rational solution divides . Abramov showed how this universal denominator can be computed by only using the first and the last coefficient polynomial and . 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

A sequence is called hypergeometric if the ratio of two consecutive terms is a rational function in , i.e. . 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.^{
[3]}

A different and more efficient approach is due to Mark van Hoeij. Considering the roots of the first and the last coefficient polynomial and – called singularities – one can build a solution step by step making use of the fact that every hypergeometric sequence has a representation of the form

^{ [7]}

^{ [8]}

### D'Alembertian solutions

A sequence is called d'Alembertian if for some hypergeometric sequences and means that where denotes the difference operator, i.e. . This is the case if and only if there are first-order linear recurrence operators with rational coefficients such that .^{
[4]}

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 . 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 . The sequence is determined by the linear recurrence equation with polynomial coefficients

^{ [10]}

### Involutions

The number of involutions of a set with elements is given by the recurrence equation

^{ [4]}

## Applications

A function is called hypergeometric if where denotes the rational functions in and . A hypergeometric sum is a finite sum of the form where 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 .^{
[4]}

## References

**^**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.**^**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**.- ^
^{a}^{b}Petkovšek, Marko (1992). "Hypergeometric solutions of linear recurrences with polynomial coefficients".*Journal of Symbolic Computation*.**14**(2–3): 243–264. doi: 10.1016/0747-7171(92)90038-6. ISSN 0747-7171. - ^
^{a}^{b}^{c}^{d}Petkovšek, Marko; Wilf, Herbert S.; Zeilberger, Doron (1996).*A=B*. A K Peters. ISBN 978-1568810638. OCLC 33898705. **^**Abramov, Sergei A.; Bronstein, Manuel; Petkovšek, Marko (1995).*On polynomial solutions of linear operator equations*.*ISSAC '95 Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation*. ACM. pp. 290–296. CiteSeerX 10.1.1.46.9373. doi: 10.1145/220346.220384. ISBN 978-0897916998.**^**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. doi: 10.1016/s0041-5553(89)80002-3. ISSN 0041-5553.**^**van Hoeij, Mark (1999). "Finite singularities and hypergeometric solutions of linear recurrence equations".*Journal of Pure and Applied Algebra*.**139**(1–3): 109–131. doi: 10.1016/s0022-4049(99)00008-0. ISSN 0022-4049.**^**Cluzeau, Thomas; van Hoeij, Mark (2006). "Computing Hypergeometric Solutions of Linear Recurrence Equations".*Applicable Algebra in Engineering, Communication and Computing*.**17**(2): 83–115. doi: 10.1007/s00200-005-0192-x. ISSN 0938-1279.**^**Abramov, Sergei A.; Petkovšek, Marko (1994).*D'Alembertian solutions of linear differential and difference equations*.*ISSAC '94 Proceedings of the International Symposium on Symbolic and Algebraic Computation*. ACM. pp. 169–174. doi: 10.1145/190347.190412. ISBN 978-0897916387.**^**"A000165 - OEIS".*oeis.org*. Retrieved 2018-07-02.