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.
is a linear recurrence operator with polynomial coefficients and
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.
is called the general solution of the homogeneous problem
In the late 1980s Sergei A. Abramov described an algorithm which finds the general polynomial solution of a recurrence equation, i.e.
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
In 1989 Sergei A. Abramov showed that a general rational solution, i.e.
Abramov showed how this universal denominator can be computed by only using the first and the last coefficient polynomial
is called hypergeometric if the ratio of two consecutive terms is a rational function in
This is the case if and only if the sequence is the solution of a first-order recurrence equation with polynomial coefficients.
In 1992 Marko Petkovšek gave an algorithm to get the general hypergeometric solution of a recurrence equation where the right-hand side
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 all possibilities one gets the general solution of the recurrence equation.
This is the case if and only if there are first-order linear recurrence operators
[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] The number of signed permutation matrices of size
The sequence is determined by the linear recurrence equation with polynomial coefficients
describes the number of signed permutation matrices.
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.
Zeilberger's creative telescoping algorithm can transform such a hypergeometric sum into a recurrence equation with polynomial coefficients.