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 , .