India — Team Selection Test, 2009

Each $a_n$ is odd for $n \ge 1$. Hence $a_{n-1} + a_{n-2}$ is even for $n \ge 3$. This implies $a_n \le (a_{n-1} + a_{n-2})/2$, for all $n \ge 3$. An easy induction shows that $a_n \ge \max\{a, b\}$, for all $n$. Thus the number of pairs of the form $\{a_{n-1}, a_{n-2}\}$ is finite. It follows that $a_n$ is eventually periodic.

Let $M$ be the largest number in the cycle into which the sequence settles. Let $u$, $v$ be the numbers preceding it. Then we see that $u \le M$, $v \le M$ and $M \le (u+v)/2$. Thus $u = v = M$. This implies that the sequence is eventually constant.

Let $d = \text{gcd}(a, b)$. Then $d$ is odd. An easy induction proves that $d|a_n$ for all $n$. Hence $d$ divides $M$. Since $a \ne b$, it cannot be the case that $a_n = M$ for all $n$. Consider the position $a_k$, $M$, $M$ in the sequence, where $a_k \ne M$. By definition of the sequence, we have
$$M = \frac{M + a_k}{2^r},$$
where $r \ge 1$. This gives $a_k = (2^r - 1)M$. Hence $M$ divides $a_k$. Now consider the position just one earlier: $a_{k-1}$, $a_k$, $M$. Again we have
$$M = \frac{a_{k-1} + a_k}{2^s},$$
for some $s \ge 1$. This gives $a_{k-1} = 2^s M - a_k$. It follows that $M$ divides $a_{k-1}$. Since $M$ is odd, induction shows that $M$ divides $a_n$ for all $n$. Hence $M$ divides $d$. We conclude that $M = d$.