Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Qiaochu Yuan Apr 13 '11 at 22:31

1 Answer 1

up vote 14 down vote accepted

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.

share|improve this answer
    
Silly me. Of course I should have checked EC... –  Qiaochu Yuan Apr 14 '11 at 3:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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