
P-recursive equation

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 formula_1 be a field of characteristic zero (for example formula_2), formula_3 polynomials for formula_4,formula_5 a sequence and formula_6 an unknown sequence. The equationformula_7is called a linear recurrence equation with polynomial coefficients (all recurrence equations in this article are of this form). If formula_8 and formula_9 are both nonzero, then formula_10 is called the order of the equation. If formula_11 is zero the equation is called homogeneous, otherwise it is called inhomogeneous.
This can also be written as formula_12 where formula_13 is a linear recurrence operator with polynomial coefficients and formula_14 is the shift operator, i.e. formula_15.
Closed form solutions.
Let formula_16 or equivalently formula_17 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: formula_18. As a subspace of the space of sequences this kernel has a basis. Let formula_19 be a basis of formula_20, then the formal sum formula_21 for arbitrary constants formula_22 is called the general solution of the homogeneous problem formula_23. If formula_24 is a particular solution of formula_17, i.e. formula_26, then formula_27 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. formula_28, with a polynomial right-hand sideformula_29. 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. 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 formula_30).
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. formula_31, with polynomial right-hand side formula_32, can be found by using the notion of a universal denominator. A universal denominator is a polynomial formula_33 such that the denominator of every rational solution divides formula_33. Abramov showed how this universal denominator can be computed by only using the first and the last coefficient polynomial formula_8 and formula_9. Substituting this universal denominator for the unknown denominator of formula_37 all rational solutions can be found by computing all polynomial solutions of a transformed equation.
Hypergeometric solution.
A sequence formula_38 is called hypergeometric if the ratio of two consecutive terms is a rational function in formula_39, i.e. formula_40. 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 formula_41 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 formula_8 and formula_9 – called singularities – one can build a solution step by step making use of the fact that every hypergeometric sequence formula_44 has a representation of the formformula_45for some formula_46 with formula_47 for formula_48 and formula_49. Here formula_50 denotes the Gamma function and formula_51 the algebraic closure of the field formula_1. Then the formula_53 have to be singularities of the equation (i.e. roots of formula_8 or formula_9). Furthermore one can compute bounds for the exponents formula_56. For fixed values formula_57 it is possible to make an ansatz which gives candidates for formula_58. For a specific formula_58 one can again make an ansatz to get the rational function formula_60 by Abramov's algorithm. Considering all possibilities one gets the general solution of the recurrence equation.
D'Alembertian solutions.
A sequence formula_37 is called d'Alembertian if formula_62 for some hypergeometric sequences formula_63 and formula_64 means that formula_65 where formula_66 denotes the difference operator, i.e. formula_67. This is the case if and only if there are first-order linear recurrence operators formula_68 with rational coefficients such that formula_69.
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.
Examples.
Signed permutation matrices.
The number of signed permutation matrices of size formula_70 can be described by the sequence formula_71. 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 formula_72. The sequence is determined by the linear recurrence equation with polynomial coefficientsformula_73and the initial values formula_74. Applying an algorithm to find hypergeometric solutions one can find the general hypergeometric solutionformula_75for some constant formula_76. Also considering the initial values, the sequence formula_77 describes the number of signed permutation matrices.
Involutions.
The number of involutions formula_38 of a set with formula_79 elements is given by the recurrence equationformula_80Applying 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 formula_81 is called hypergeometric if formula_82 where formula_83 denotes the rational functions in formula_79 and formula_85. A hypergeometric sum is a finite sum of the form formula_86 where formula_81 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 formula_11.