# 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)