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.



Integer sequences and integer coefficients in recurrence relations.
This is *Fatou's lemma*. One reference is Exercise 4.1(a) of my book *Enumerative Combinatorics*, vol. 1. This is repeated as Exercise 4.2(a) at <http://math.mit.edu/~rstan/ec/ec1.pdf>.


