Writeup: IMO 2004 SL A2

03 Jun, 2025

Hey everyone! I haven't posted here in a while because I've been busy with finals and starting my summer research, but I'm glad I finally have time to sit down and revive this blog again. Here's my solution for A2 on the 2004 IMO Shortlist.

Problem Statement:

Let $a_{0}$ , $a_{1}$ , $a_{2}$ , ... be an infinite sequence of integers satisfying the equation $a_{n} = | a_{n + 1} - a_{n + 2} |$ for all $n \geq 0$ , where $a_{0}$ and $a_{1}$ are two different positive integers.

Can this sequence $a_{0}$ , $a_{1}$ , $a_{2}$ , ... be bounded?

My Solution:

First, a couple facts to note:

All $a_{i}$ must be nonnegative, since they are the absolute value of a number.
We can either have $a_{n + 2} = a_{n} + a_{n + 1},$ or $a_{n + 2} = a_{n + 1} - a_{n}$ . From the first fact (above), if $a_{n} \geq a_{n + 1}$ , we must have $a_{n + 2} = a_{n} + a_{n + 1} .$ The latter equivalence makes $a_{n + 2}$ negative.
It is impossible to have $a_{i} = 0$ , and it is also impossible to have $a_{i} = a_{i + 1}$ . What follows is the proof of this fact.

Proof:

First, we prove it's impossible to have $a_{i} = a_{i + 1}$ . For the sake of contradiction, assume there exists $i$ such that $a_{i} = a_{i + 1}$ . Then there exists minimal $i$ with $a_{i} = a_{i + 1}$ . We can assume $i \geq 3$ since $a_{0} \neq a_{1}$ , $a_{1} \neq a_{2}$ since $| a_{1} - a_{2} | = a_{0} \neq 0$ , and $a_{3} \neq a_{2}$ since $| a_{3} - a_{2} | = a_{1} \neq 0$ .

Since $i \geq 3$ , this would imply that $a_{i - 1} = 0$ , which would imply that $a_{i - 3} = | a_{i - 2} - a_{i - 1} | = a_{i - 2}$ since $a_{i - 2}$ is positive, which would imply the existence of a smaller $j = i - 3$ such that $a_{j} = a_{j + 1}$ . Contradiction!

Now, we proceed with the proof. Let $D = {i | a_{i} > a_{i + 1}}$ . Note that if $| D |$ is finite, then $\exists N$ such that $\forall n \geq N$ , $a_{n} < a_{n + 1}$ . If $a_{n} < a_{n + 1} < a_{n + 2}$ , then we must have $a_{n + 2} = a_{n + 1} + a_{n}$ for all $n \geq N$ , which obviously diverges and is not bounded.

Now, assume that $| D |$ is instead infinite. Number the $i$ in $| D |$ from smallest to largest as $i_{k}$ . Then note that $i_{k + 1} - i_{k} \geq 2$ since if $a_{i_{k}} > a_{i_{k} + 1}$ , then $a_{i_{k} + 2} = a_{i_{k} + 1} + a_{i_{k}} > a_{i_{k} + 1}$ .

Now note that $a_{i_{k}}$ is a strictly increasing quantity.

Proof: Note that $\forall j$ such that $i_{k} < j < i_{k + 1}$ , we must have $a_{j} < a_{j + 1}$ . Note, also that $a_{i_{k} + 2} = a_{i_{k}} + a_{i_{k} + 1} > a_{i_{k}} .$ This implies that $a_{i_{k + 1}} > a_{i_{k}}$ . Since the integers are closed under addition, this means that we must have $a_{i_{k + 1}} \geq a_{i_{k}} + 1$ , so $a_{i_{k}}$ must be unbounded and therefore $a$ is unbounded.