2013 IMO Problems/Problem 1
Problem
Prove that for any pair of positive integers and , there exist positive integers (not necessarily different) such that
.
Solution
We prove the claim by induction on .
Base case: If then , so the claim is true for all positive integers .
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 , .