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.…