I decided that I wanted to improve my mathematical problem solving and proof writing skills. The first question of the 2013 International Mathematics Olympiad seemed like a good place to start. I found the idea for a messy solution in about half an hour, but I could tell that there was a simple solution I was missing. After thinking about the problem in different angles for a few hours I finally managed to write up a solution I was happy with!
Prove that for all positive integers , , there exist positive integers , such that,
We prove the claim by induction on .
Base case: If then , so the claim is true for all .
Inductive hypothesis: Suppose that for some the claim is true for , for all .
Inductive step: Let be arbitrary and fixed. Case on the parity of :
[Case 1: is even]
[Case 2: is odd]
In either case, for some .
By the induction hypothesis we can choose such that .
Therefore, since was arbitrary, the claim is true for , for all . Our induction is complete and the claim is true for all positive integers , .