Talk:2012 USAMO Problems/Problem 4
Though not as elegant as the inductive proof, my proof for this problem is quite different from the one posted in the Page, so I would like to paste it here just for reference.
1. First, ,
equal to
or
.
2. Second, suppose that for all ,
. Then for
,
(
is an integer.)
, therefore
and so
is the only possibility. Hence
. Similar argument yields that
, so
is a constant function, which can only be
or
.
3. From now on, suppose that there exists such that
.
4. By and that
we know that
, or
.
5. By we know that
, and by
and
we know that
, therefore
.
6. Then by we know that
is odd, so
.
7. For ,
implies that
, otherwise
and that
, which is a contradiction. Since
, now we have
, so
. Now we have a lower bound. What is more difficult is to find an upper bound of
.
(I know from the main Page it is not too hard to get the upper bound, but to be honest it takes me quite a while to figure it out.)
8. Therefore . Now
, therefore if
, then suppose
, then we have
, which is not divisible by and so
. By induction we have
for all
.
--Lightest 22:26, 3 May 2012 (EDT)