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 ,
, where is an integer. We have 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 let and we have
, where the right hand side should not be divisible by and so . By induction we have for all .
--Lightest 22:26, 3 May 2012 (EDT)