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.

  • $\begingroup$ I think this is well-known, but somewhat tedious. The generalization to any finite-order linear recurrence is also true. I think this has also come up on MO before. $\endgroup$ Apr 13 '11 at 22:31

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.

  • $\begingroup$ Silly me. Of course I should have checked EC... $\endgroup$ Apr 14 '11 at 3:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.