2001 IMO Shortlist Problems/A5
Problem
Find all positive integers such that
where and for .
Solution
We claim that there is only one such sequence: . This works because
It is also easy to check that for .
Now we prove such a sequence is unique. We first claim that a sequence of positive integers satisfying for has the property that We use induction on the length of the sequence. The base case is trivial (the condition guarantees that ). For the inductive step, notice that by the inductive hypothesis, so it suffices to show but this is equivalent to which we know to be true.
Now suppose there were two sequences and that satisfied the conditions in the problem. Clearly one cannot be a subsequence of the other, or else the longer one will obviously have a larger sum. So there exists a smallest integer such that (so for , ). Without loss of generality, let .
By our previous claim, we have that and as a corollary, since the first terms are equal, which contradicts the fact that they are equal. So there is a unique sequence satisfying the problem conditions.