1973 USAMO Problems/Problem 2
Contents
Problem
Let and denote two sequences of integers defined as follows:
Thus, the first few terms of the sequences are:
Prove that, except for the "1", there is no term which occurs in both sequences.
Solution
We can look at each sequence :
- Proof that repeats :
The third and fourth terms are and . Plugging into the formula, we see that the next term is , and plugging and , we get that the next term is . Thus the sequence repeats, and the pattern is .
- Proof that repeats :
The first and second terms are and . Plugging into the formula, we see that the next term is , and plugging and , we get that the next term is . Thus the sequence repeats, and the pattern is .
Combining both results, we see that and are not congruent when and . Thus after the "1", the terms of each sequence are not equal.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Solution 2
We can solve this problem by finding a particular solution for each linear recurrence.
with characteristic polynomial
, so
After plugging in to find the particular solution:
and , so
Doing the same for , we get
We know they're equal at , so let's set them equal and compare.
By induction, we know in general that for all , so for all .
Therefore, the left hand side is always increasing and will never equal 5 again, so equality between and only holds when , so they only share 1 term.
See Also
1973 USAMO (Problems • Resources) | ||
Preceded by Problem 1 |
Followed by Problem 3 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.