South African Mathematical Olympiad Third Round

We claim that the only possible sequences are the following:
* $a_n = n - 1$ for all $n$, or
* $a_n = \frac{n^2+n}{2} + k$ for all $n$, where $k$ is a fixed nonnegative integer, or
* $a_n = \begin{cases} n-1 & n \le N, \\ \frac{n^2+n}{2} - \frac{N^2-N+2}{2} & n > N, \end{cases}$ where $N$ is a fixed nonnegative integer.

Let us first verify that each of these sequences satisfies the conditions:
* If $a_n = n - 1$ for all $n$, then $a_{n-1} + n = 2n - 2 = 2a_n$ is indeed divisible by $a_n$.
* If $a_n = \frac{n^2+n}{2} + k$ for all $n$, then $a_{n-1} + n = \frac{n^2-n}{2} + k + n = \frac{n^2+n}{2} + k = a_n$ is also divisible by $a_n$.
* In the third case, $a_n$ divides $a_{n-1} + n$ for $n \le N$ as in the first case. Next note that $a_{N+1} = \frac{(N+1)^2+(N+1)}{2} - \frac{N^2-N+2}{2} = 2N$ divides $a_N + (N+1) = 2N$. Finally, for $n > N+1$, we have $a_n = a_{n-1} + n$ as in the second case, so $a_n$ again divides $a_{n-1} + n$.

Now we prove that these are the only such sequences. First, let $a_k$ be an element of the sequence such that $a_k \ge k$ (if such an element exists). Recall that $a_k + k + 1$ has to be a multiple of $a_{k+1}$. However, since $a_{k+1} > a_k$, we have
$$2a_{k+1} \ge 2(a_k + 1) > 2a_k + 1 \ge a_k + k + 1.$$
So the only possible multiple of $a_{k+1}$ that $a_k + k + 1$ could be is $1 \cdot a_{k+1}$, and it follows that $a_{k+1} = a_k + k + 1$. But then $a_{k+1} \ge k + k + 1 \ge k + 1$, so we can repeat the argument with $k+1$ instead of $k$ to show that $a_{k+2} = a_{k+1} + k + 2$, etc. Generally, we get $a_{n+1} = a_n + n + 1$ for all $n \ge k$.

If $a_1 \ge 1$, then we can invoke this observation immediately: $a_{n+1} = a_n + n + 1$ for all $n \ge 1$, so
$$a_n = a_{n-1} + n = a_{n-2} + (n-1) + n = \dots = a_1 + 2 + 3 + \dots + (n-1) + n = \frac{n^2+n}{2} + (a_1 - 1),$$
which is exactly our second solution.

Suppose finally that $a_1 = 0$, and let $N$ be the largest index for which $a_N = N - 1$; if there is no largest index, then $a_n = n - 1$ for all $n$, and we obtain the first solution. Next note that $a_{N+1}$ has to divide $a_N + N + 1 = 2N$. By our choice of $N$, we have $a_{N+1} \ne N$, and since $a_{N+1} > a_N = N - 1$, the only possible value (the only divisor of $2N$) for $a_{N+1}$ is $2N$. But then $a_{N+1} = 2N \ge N + 1$, and we can apply the same observation as before: $a_{m+1} = a_m + m + 1$ for all $m \ge N$, thus
$$a_n = a_{n-1} + n = \dots = a_N + (N+1) + (N+2) + \dots + (N-1) + n = \\ = (N-1) + \frac{n^2+n}{2} - \frac{N^2+N}{2} = \frac{n^2+n}{2} - \frac{N^2-N+2}{2}$$
for all $n > N$, which is indeed the third solution.