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\).