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?