, 2009

Let $D$ be the common difference of the progression $s_{s_1}, s_{s_2}, s_{s_3}, \dots$. Also, define $d_n = s_{n+1} - s_n$. For every $n$, $d_n \ge 1$ because $s_1, s_2, s_3, \dots$ is strictly increasing. Therefore, for all $i < j$, we have
$$s_j - s_i = d_i + d_{i+1} + \dots + d_{j-1} = \sum_{k=i}^{j-1} d_k \ge \sum_{k=i}^{j-1} 1 = j - i. \quad (1)$$
Taking $i = s_n$ and $j = s_{n+1}$ gives $D = s_{s_{n+1}} - s_{s_n} \ge d_n$ for any $n$.
Thus, the sequence of integers $d_1, d_2, d_3, \dots$ is bounded both above (by $D$) and below (by 1), so it
has a maximum and a minimum value. Call these values $M$ and $m$ respectively; that is, define
$m = \min\{d_1, d_2, \dots\} \text{ and } M = \max\{d_1, d_2, \dots\}.$

If $M = m$, then all the $d_n$ are equal, and we are done.
Now we approach indirectly by assuming that $M \neq m$, and seeking a contradiction.
For all $i < j$, we have
$$s_j - s_i = d_i + d_{i+1} + \dots + d_{j-1} \leq M(j - i).$$
By definition of $m$, there exists $n$ such that $s_{n+1} - s_n = m$, and so
$$D = s_{s_{n+1}} - s_{s_n} \leq M(s_{n+1} - s_n) = Mm. \qquad (2)$$
Moreover, if equality holds, then $d_{s_n}, d_{s_{n+1}}, \dots, d_{s_{n+1}-1}$ must all equal $M$.
Likewise, for all $i < j$, we can see that $s_j - s_i \geq m(j - i)$. There exists $n$ such that $s_{n+1} - s_n = M$, and so
$$D = s_{s_{n+1}} - s_{s_n} \geq m(s_{n+1} - s_n) = Mm. \qquad (3)$$
If equality holds, then $d_{s_n}, d_{s_{n+1}}, \dots, d_{s_{n+1}-1}$ must all equal $m$.
Clearly, (2) and (3) imply $D = Mm$.
Now, we claim that for every $n$ such that $d_n = m$, there exists $n' > n$ such that $d_{n'} = M$ — namely, $n' = s_n$. Indeed, from the equality in (2), we must have $d_{s_n} = M$. And by (1), $s_n \geq s_1 + n - 1 \geq n$; moreover, since $d_{s_n} \neq d_n$, we cannot have $s_n = n$, so $s_n > n$ strictly. Similarly, using (3), for every $n$ such that $d_n = M$, there exists $n' > n$ such that $d_{n'} = m$ — again given by $n' = s_n$.
Iteratively applying these two facts, we see that there are infinitely many values of $n$ for which $d_n = m$ and infinitely many values of $n$ for which $d_n = M$. These imply, in turn, that there are infinitely many values of $n$ for which $d_{s_n} = M$, and infinitely many values of $n$ for which $d_{s_n} = m$.
Now, the two sequences $s_{s_1}, s_{s_2}, s_{s_3}, \dots$ and $s_{s_{1+1}}, s_{s_{2+1}}, s_{s_{3+1}}, \dots$ are both arithmetic progressions; therefore, when we take differences of corresponding terms, we again get an arithmetic progression. This sequence of differences is just
$$d_{s_1}, d_{s_2}, d_{s_3}, \dots$$
We saw that this sequence contains infinitely many $m$'s and infinitely many $M$'s. But an arithmetic progression cannot have even two terms equal to each other unless it is constant. It follows that $M = m$, as required.