The final round of the South African Mathematics Olympiad will be taking place on Thursday, 28 July 2019. I have been writing about some of the problems from the senior paper from 2018. A list of all of the problems can be found here.

Today we will look at the fifth problem from the 2018 South African Mathematics Olympiad:

Determine all sequences $a_1, a_2, a_3, \ldots$ of nonnegative integers such that $a_1 < a_2 < a_3 < \ldots$, and $a_n$ divides $a_{n - 1} + n$ for all $n \geq 2$.

Since the sequence $a_1, a_2, \ldots$ is strictly increasing, we know that $a_n \geq n - 1$ for all positive integers $n$. (We could prove this rigorously by induction.) This means that $a_{n - 1} + n \leq (a_n - 1) + (a_n + 1) = 2a_n$ for all $n$, and so we know that $a_{n - 1} + n$ is equal to either $a_n$, or to $2a_n$ for all positive integers $n$. Perhaps we should try to figure out exactly when it is equal to $a_n$, and when it is equal to $2a_n$. If we knew, for example, that we always have that $a_{n - 1} + n = a_n$, then we have reduced the problem to solving this recurrence relation.

So when is it possible that $a_{n - 1} + n = 2a_n$? Looking at our derivation above, we see that $a_{n - 1} + n$ is always strictly smaller than $2a_n$ unless both $a_{n - 1} = a_n - 1$ and $a_n = n - 1$. i.e. We must have equality in each of the two inequalities that we used.

We see that if there is some positive integer $k$ such that $a_{k - 1} + k = 2a_k$, then we must have that $a_k = k - 1$, and so, since the sequence is strictly increasing, we have that $a_n = n - 1$ for all $n \leq k$. The sequence thus has some initial segment where $a_n = n - 1$, and then possibly switches to a sequence where $a_{n - 1} + n = a_n$. In fact, it is possible that this switch never occurs. We could have that $a_n = n - 1$ for all positive integers $n$. This is in fact a solution to the problem. We verify that if $a_n = n - 1$ for all positive integers $n$, then $a_{n - 1} + n = 2n - 2 = 2a_n$ for all $n$.

We now turn our attention to finding all of the possible sequences where either there is no positive integer $n$ such that $a_n = n - 1$, or where there is some positive integer $k$ such that $a_k \geq k$, but $a_n = n - 1$ for all $n < k$.

Suppose that there are no positive integers $n$ such that $a_n = n - 1$. We then have that $a_n = a_{n - 1} + n$ for all positive integers $n$. This implies that

$\displaystyle a_n = a_{n - 1} + n = a_{n - 2} + (n - 1) + n = \cdots = a_1 + 2 + 3 + \cdots + n$

for all positive integers $n$. We recall, or learn, that the sum of the first $n$ positive integers is $\frac{n(n + 1)}{2}$, and so we find that

$\displaystyle a_n = a_1 - 1 + \frac{n(n + 1)}{2} = a_1 + \frac{(n + 2)(n - 1)}{2}$

for all positive integers $n$. To be more rigorous, we could prove this using the principle of mathematical induction. By construction, this satisfies $a_n = a_{n - 1} + n$ for all $n \geq 2$, and so this is a valid solution to the problem for all values of $a_1$.

Finally, what sequences arise if there is some positive integer $k$ such that $a_k \geq k$, but $a_n = n - 1$ for all $n < k$? Since $a_k \geq k$ and the sequence is strictly increasing, we have that $a_n \geq n$ for all positive integers $n \geq k$. We thus have that $a_n = a_{n - 1} + n$ for all $n > k$, and so we find using a similar argument to before that

$\displaystyle a_n = a_k + (k + 1) + (k + 2) + \cdots + n = a_k + \frac{n(n + 1)}{2} - \frac{k(k + 1)}{2}$

for all positive integers $n \geq k$.

Thus we potentially have a solution where for some positive integer $k$, we have that $a_n = n - 1$ for $n < k$, and $a_n = a_k + \frac{1}{2} n(n + 1) - \frac{1}{2} k(k + 1)$ for $n \geq k$. The conditions of the problem are clearly satisfied for $n < k$, since for these values of $n$ we have that $a_{n - 1} + n = 2a_n$, and by construction, we have that $a_{n} = a_{n - 1} + n$ for all $n > k$. Thus the only requirement that needs to be satisfied for this to be a valid solution is that $a_k$ divides $a_{k - 1} + k$. We thus require that $a_k$ divides $2k - 2$. Since we have that $a_k \geq k$, we must in fact have that $a_k = 2k - 2$. (We have that $2a_k \geq 2k > 2k - 2$, and so the multiple of $a_k$ that $2k - 2$ is equal to must be $a_k$ itself.)

In summary, we found that all sequences that satisfy the conditions in the problem are given by

• $a_n = n - 1$ for all positive integers $n$; or
• $\displaystyle a_n = a_1 + \frac{(n + 2)(n - 1)}{2}$ for all positive integers $n$, where the value of $a_1$ can be chosen arbitrarily; or
• There is some positive integer $k$ such that $a_n = n - 1$ for $n < k$, and $\displaystyle a_n = \frac{n(n + 1)}{2} - \frac{k(k + 1)}{2} + 2k - 2$ for all $n \geq k$.
 How clear is this post?