Polynomial solutions

In the late 1980s Sergei A. Abramov described an algorithm which finds the general polynomial solution of a recurrence equation, i.e. ${\textstyle y(n)\in \mathbb {K} [n]}$, with a polynomial right-hand side${\textstyle f(n)\in \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.^[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 ${\textstyle (x^{n})_{n\in \mathbb {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

In 1989 Sergei A. Abramov showed that a general rational solution, i.e. ${\textstyle y(n)\in \mathbb {K} (n)}$, with polynomial right-hand side ${\textstyle f(n)\in \mathbb {K} [n]}$, can be found by using the notion of a universal denominator. A universal denominator is a polynomial ${\textstyle u}$ such that the denominator of every rational solution divides ${\textstyle u}$. Abramov showed how this universal denominator can be computed by only using the first and the last coefficient polynomial ${\textstyle p_{0}}$ and ${\textstyle p_{r}}$. Substituting this universal denominator for the unknown denominator of ${\displaystyle y}$ all rational solutions can be found by computing all polynomial solutions of a transformed equation.^[6]

Hypergeometric solution

A sequence ${\textstyle y(n)}$ is called hypergeometric if the ratio of two consecutive terms is a rational function in ${\displaystyle n}$, i.e. ${\textstyle y(n+1)/y(n)\in \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 ${\displaystyle 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.^[3]

A different and more efficient approach is due to Mark van Hoeij. Considering the roots of the first and the last coefficient polynomial ${\textstyle p_{0}}$ and ${\textstyle p_{r}}$ – called singularities – one can build a solution step by step making use of the fact that every hypergeometric sequence ${\textstyle y(n)}$ has a representation of the form

$${\displaystyle y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}}$$

for some ${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$ with ${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$ for ${\textstyle i\neq j}$ and ${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$. Here ${\textstyle \Gamma (n)}$ denotes the Gamma function and ${\textstyle {\overline {\mathbb {K} }}}$ the algebraic closure of the field ${\textstyle \mathbb {K} }$. Then the ${\textstyle \xi _{1},\dots ,\xi _{s}}$ have to be singularities of the equation (i.e. roots of ${\textstyle p_{0}}$ or ${\textstyle p_{r}}$). Furthermore one can compute bounds for the exponents ${\textstyle e_{i}}$. For fixed values ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$ it is possible to make an ansatz which gives candidates for ${\textstyle z}$. For a specific ${\textstyle z}$ one can again make an ansatz to get the rational function ${\textstyle 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 ${\displaystyle y}$ is called d'Alembertian if ${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$ for some hypergeometric sequences ${\textstyle h_{1},\dots ,h_{k}}$ and ${\textstyle y=\sum x}$ means that ${\textstyle \Delta y=x}$ where ${\textstyle \Delta }$ denotes the difference operator, i.e. ${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$. This is the case if and only if there are first-order linear recurrence operators ${\textstyle L_{1},\dots ,L_{k}}$ with rational coefficients such that ${\textstyle L_{k}\cdots L_{1}y=0}$.^[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]

Signed permutation matrices

The number of signed permutation matrices of size ${\displaystyle n\times n}$ can be described by the sequence ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {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 ${\textstyle \pm 1}$. The sequence is determined by the linear recurrence equation with polynomial coefficients

$${\displaystyle y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)}$$

and the initial values ${\textstyle y(0)=1,y(1)=2}$. Applying an algorithm to find hypergeometric solutions one can find the general hypergeometric solution

$${\displaystyle y(n)=c\,2^{n}n!}$$

for some constant ${\textstyle c}$. Also considering the initial values, the sequence ${\textstyle y(n)=2^{n}n!}$ describes the number of signed permutation matrices.^[10]

Involutions

The number of involutions ${\textstyle y(n)}$ of a set with ${\textstyle n}$ elements is given by the recurrence equation

$${\displaystyle y(n)=(n-1)\,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.^[4]