USAMO 1973 #2 August 11, 2009
Posted by lumixedia in Problem-solving.
Tags: algebra, contest math, number theory, olympiad math, USAMO, USAMO 1973
trackback
USAMO 1973 #2. Let 
and 
denote two sequences of integers defined as follows:
Thus, the first few terms of the sequence are:
Prove that, except for “1”, there is no term which occurs in both sequences.
Solution 1. After the first two terms, the 
become the sequence 
and the 
become the sequence 
. These patterns will continue since the same linear combination of the same residues mod 8 always yields the same residue mod 8. So no number other than 1 can appear in both sequences.
I inexplicably came up with a different solution first, which is completely pointless in comparison, but here it is anyway.
Solution 2. Solving the characteristic equations of the two recursions and plugging in the first couple of terms gives the closed formulas 
and 
. (I don’t want to go into very much detail here because I don’t completely understand why this works. A quick Googling comes up with a generating functions/partial fraction decomposition explanation for the second-order case used here, which probably makes sense for higher-order recursions too.)
So we need to prove that we cannot have 
for any positive integers 
. Suppose for the sake of contradiction that some pair satisfies this equation. Comparing the two sides mod 4, we have 
, or 
, so we can conclude that 
. We have two cases: 
and 
.
In the first case, we have 
, or 
, or 
. This is impossible since the LHS is the difference of two positive squares.
In the second case, we have 
, or 
, or 
. Unless 
, this becomes 
, again a contradiction. We conclude that there are no such , as desired.
Like this:
Like Loading...
Perhaps I’m missing something obvious, but what is the motivation for looking at the sequence mod 8? [Besides, of course, that it works to solve the problem.]
The factors of two in both recursions might clue you in, but I agree that it’s not an obvious step; at least for me, I wouldn’t have tried it until I wrote down the closed forms.
As for this linear recurrence business, this is pretty much one of my favorite subjects ever; there’s a relevant section of this PDF you might be interested in, and I’ve also written several posts and given a talk on the subject. Let me just say that partial fraction decomposition is by no means the only way to think about these things.
Behavior in some mod in general seems like a reasonable way to simplify the sequences–my very first reaction was to wonder what they looked like mod 3 and 4–and then I guess you test moduli until you find one that works. I did not try that, instead opting to find the closed forms and mess around with them (glad to hear I’m not the only one who would have taken that path). I know of the mod 8 solution because I read the official solution packet.
Thanks for the links! They look really cool so far