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>