USAMO 1973 #2 August 11, 2009Posted by lumixedia in Problem-solving.
Tags: algebra, contest math, number theory, olympiad math, USAMO, USAMO 1973
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.