On the representation of C-recursive integer sequences by arithmetic terms

We show that, if an integer sequence is given by a linear recurrence of constant rational coefficients, then it can be represented as the difference of two arithmetic terms with exponentiation, which do not contain any irrational constant. We apply our methods to various Lucas sequences including the classical Fibonacci sequence, to the sequence of solutions of the Pell equation and to some natural C-recursive sequences of degree 3.