Rational Solutions of Linear Difference Equations
This paper contains a new bound for the denominator of
rational solutions of (systems of) difference equations.
The bound is sharper than other known bounds, in particular
if all solutions are rational then the bound is exact.
In the paper the bound is given by the valuation (i.e. the
pole and root orders) in
a certain matrix. I have implemented the bound for the
case of a scalar equation, and I use some tricks to get
these pole orders quickly without doing costly matrix
products. This is used in my
implementation for hypergeometric solutions.
An illustration how to do such computations for a scalar equation
is given in Example 2
in the paper Set of Poles of Solutions of Linear Difference Equations with Polynomial
Coefficients,
other examples and additional explanations on this are found in the
papers listed here.
Download this paper.