Background: As a result of teaching recurrence relations in various courses over the years, I am working on a paper on periodic integer sequences generated by second-order, linear, homogeneous recurrences with constant coefficients.
Briefly, if the recurrence generates a sequence of integers, must the coefficients be integers?
More precisely: Consider the recurrence defined by $G_{n+2} = r G_{n+1} + s G_n$, with $G_0$ and $G_1$ given integers. Suppose no lower-order recurrence generates $G$, and further, that $G$ is a sequence of integers. Must $r$ and $s$ be integers?
(1) The condition about lower-order is required. It is not hard to come up with 0th- or 1st-order examples which can also be generated by second-order recurrences with non-integer coefficients.
(2) It is not hard to see that $s$ must be an integer. A simple induction proof shows that for all $n\ge0$, $G_n G_{n+2} - G_{n+1}^2=(-s)^n(G_0 G_2 - G_1^2)$, from which is follows easily that $s$ is an integer.
(3) It seems that it should be easy to show that $r$ is an integer. However, by working backwards, it is not difficult to find a sequence generated by $G_{n+2} = G_{n+1} / 2 + G_n$ which begins with an arbitrary number of integers, the last of which is odd, so that the next term is not an integer. $G_0 = 32$ and $G_1 = 64$ give 311 as the 8th term. If $p$ is a prime factor of the denominator of $r$, it seems that the powers of $p$ in $G_n$ should eventually decrease by at least one (possibly more, if the power of $p$ dividing the denominator of $r$ is greater than 1) each time.
This problem has been nagging me for a while now. I'm not a number theorist (interests lie mainly with polyhedral geometry and education), so I apologize if there is a well-known result which proves this. The extension to sequences of integers generated by higher-order recurrences should be clear, so if there is a general result in such cases, that would be nice, too.
