The 2018 South African Mathematics Olympiad — Problem 5
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
of nonnegative integers such that
, and
divides
for all
.
Since the sequence is strictly increasing, we know that
for all positive integers
. (We could prove this rigorously by induction.) This means that
for all
, and so we know that
is equal to either
, or to
for all positive integers
. Perhaps we should try to figure out exactly when it is equal to
, and when it is equal to
. If we knew, for example, that we always have that
, then we have reduced the problem to solving this recurrence relation.…