In mathematics, particularly in computer algebra, Abramov's algorithm computes all rational solutions of a linear recurrence equation with polynomial coefficients.
The algorithm was published by Sergei A. Abramov in 1989.
[1][2] The main concept in Abramov's algorithm is a universal denominator.
dis ( p , q ) = max { k ∈
deg ( gcd ( p ( n ) , q ( n + k ) ) ) ≥ 1 } ∪ { − 1 } ,
denotes the set of non-negative integers.
The dispersion can be computed as the largest non-negative integer root of the resultant
be a recurrence equation of order
, polynomial right-hand side
and rational sequence solution
{\textstyle D=\operatorname {dis} (p_{r}(n-r),p_{0}(n))}
denotes the falling factorial of a function.
can be used as a denominator for all rational solutions
and hence it is called a universal denominator.
be a recurrence equation with polynomial coefficients and
a universal denominator.
ℓ ( n ) = lcm ( u ( n ) , … , u ( n + r ) )
the recurrence equation is equivalent to
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.
can then be used again to compute the rational solutions
[2] The homogeneous recurrence equation of order
It can be computed by considering the dispersion
{\displaystyle D=\operatorname {dis} (p_{1}(n-1),p_{0}(n))=\operatorname {disp} (-n,n-1)=1.}
This yields the following universal denominator:
ℓ ( n ) = lcm ( u ( n ) , u ( n + 1 ) ) = ( n − 1 ) n ( n + 1 ) .
Multiplying the original recurrence equation with
This equation has the polynomial solution
for an arbitrary constant
the general rational solution is