The main concept in Abramov's algorithm is a universal denominator. Let be a field of characteristic zero. The dispersion of two polynomials is defined as
where denotes the set of non-negative integers. Therefore the dispersion is the maximum such that the polynomial and the -times shifted polynomial have a common factor. It is if such a does not exist. The dispersion can be computed as the largest non-negative integer root of the resultant .[3][4] Let be a recurrence equation of order with polynomial coefficients , polynomial right-hand side and rational sequence solution . It is possible to write for two relatively prime polynomials . Let and
where denotes the falling factorial of a function. Then divides . So the polynomial can be used as a denominator for all rational solutions and hence it is called a universal denominator.[5]
Let again be a recurrence equation with polynomial coefficients and a universal denominator. After substituting for an unknown polynomial and setting the recurrence equation is equivalent to
As the cancel this is a linear recurrence equation with polynomial coefficients which can be solved for an unknown polynomial solution . There are algorithms to find polynomial solutions. The solutions for can then be used again to compute the rational solutions . [2]
algorithm rational_solutions is
input: Linear recurrence equation .
output: The general rational solution if there are any solutions, otherwise false.
Solve for general polynomial solution
if solution exists then
return general solution
else
return false
end if
The homogeneous recurrence equation of order
over has a rational solution. It can be computed by considering the dispersion
This yields the following universal denominator:
and
Multiplying the original recurrence equation with and substituting leads to
This equation has the polynomial solution for an arbitrary constant . Using the general rational solution is
for arbitrary .
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. Man, Yiu-Kwong; Wright, Francis J. (1994). "Fast polynomial dispersion computation and its application to indefinite summation". Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '94. pp. 175–180. doi:10.1145/190347.190413. ISBN 978-0897916387. S2CID 2192728. Chen, William Y. C.; Paule, Peter; Saad, Husam L. (2007). "Converging to Gosper's Algorithm". arXiv:0711.3386 [math.CA].