Baltic Way 1997 · Problem 5

Solution:

Suppose $u_{n}>a$. Then, if $u_{n}$ is even we have $u_{n+1}=\frac{1}{2} u_{n}<u_{n}$, and if $u_{n}$ is odd we have $u_{n+1}=a+u_{n}<2 u_{n}$ and $u_{n+2}=\frac{1}{2} u_{n+1}<u_{n}$. Hence the iteration results in $u_{n} \leqslant a$ in a finite number of steps. Thus for any non-negative integer $m$, some non-negative integer $n>m$ satisfies $u_{n} \leqslant a$, and there must be an infinite set of such integers $n$.

Since the set of natural numbers not exceeding $a$ is finite and such values arise in the sequence $\left(u_{n}\right)$ an infinite number of times, there exist nonnegative integers $m$ and $n$ with $n>m$ such that $u_{n}=u_{m}$. Starting from $u_{m}$ the sequence is then periodic with a period dividing $n-m$.