Diophantine representations of linear recurrences. I

Direct constructions of Diophantine representations of linear recurrent sequences are discussed. These constructions generalize already known results for second-order recurrences. Some connections of this problem with the theory of units in rings of algebraic integers are shown. It is proved that the required representations exist only for second-, third-, and fourth-order sequences. In the two last-mentioned cases certain additional restrictions on their coefficients must be imposed. Bibliography:14 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 227, 1995, pp. 52–60.