2001 USA TST Problems/Problem 8
Problem
(Titu Andreescu) Find all pairs of nonnegative integers such that
Solution
All solutions are consecutive pairs of one of the sequences given recursively by and
Call a solution primitive if there is no solution with and no solution with . Since the given equation is of degree 2, for any integer , there exist at most two integers such that and are solutions; it follows that every solution is a pair of consecutive terms in a sequence in which the first two terms form a primitive solution, and any two consecutive terms constitute a solution.
Now, suppose is a primitive solution, with . Rearranging the given equation, we see so is the smaller of the two nonnegative integer roots of the polynomial for if one root of this polynomial is a nonnegative integer, then so is the other.
The other root is evidently . It follows that . Therefore . If , then the only root of this polynomial is 5; if , then the roots of this polynomial are 1 and 16; if , then its roots are not integers. Therefore and are the only primitive solutions.
Now for any , the roots of are the values of for which are the given equation; and these two roots satisfy . Hence the recursive relations given at the beginning of the problem give all solutions, as desired. We may note that the sequence are the sequences and , where is the Fibonacci sequence and is the Lucas sequence.
Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.
Resources
- 2001 USA TST Problems
- <url>Forum/viewtopic.php?t=24857 Discussion on AoPS/MathLinks</url>
- <url>Forum/viewtopic.php?t=4999 Further discussion</url>