1990 USAMO Problems/Problem 2
Contents
[hide]Problem
A sequence of functions is defined recursively as follows:
(Recall that
is understood to represent the positive square root.) For each positive integer
, find all real solutions of the equation
.
Solution 1
We define . Then the recursive relation holds for
, as well.
Since for all nonnegative integers
, it suffices to consider nonnegative values of
.
We claim that the following set of relations hold true for all natural numbers and nonnegative reals
:
To prove this claim, we induct on
. The statement evidently holds for our base case,
.
Now, suppose the claim holds for . Then
The claim therefore holds by induction. It then follows that for all nonnegative integers
,
is the unique solution to the equation
.
Solution 2
We claim that the only solution is for all such
. To show this, we consider all
and find solutions
.
Before we consider solutions, we show that for all ,
is positive for all positive integers
by induction. For our base case:
so it is positive. Next, for our inductive step, assume for some
that
is positive; thus
, and we show that
is positive:
thus
, so we have proven the claim by induction.
First, we consider negative . We know that for negative
, if the equation were to have a solution, we would have
for some
. However,
is always nonnegative since
is always the square root of some number, which can never be negative; thus there are no solutions in this case.
Next, we consider . Solutions would have to satisfy
; we have previously shown that all
are positive, so there are no such
.
Finally, we consider positive . We divide this set into three groups:
,
, and
. We claim that for increasing
,
is decreasing, constant, and increasing, respectively, and we prove this using induction. First, we analyze
. Then
For our base case:
Thus
. For our inductive step, if for some
we have
, we show that
:
Thus
and the conclusion follows.
Next, for ,
by substituting. Then, if
, we show that
as well:
so the sequence is constant. Notice that in this case, the equation we must solve becomes
, which is true for all positive integers
.
Finally, we analyze . Then
For our base case:
Thus
. For our inductive step, if for some
we have
, we show that
:
Thus
and the conclusion follows.
If for some positive integer we have
, then:
is a solution, then we must have
; substituting values yields
, which implies
; this is a contradiction. Similarly, if
is a solution, then we must have
; substituting values yields
, which implies
; this is also a contradiction.
As a result, since we have already established that is a solution for all
and no other
can be solutions, we conclude that for each positive integer
, the only real solution of the equation is
.
See Also
1990 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.