Problem

Source: Spain Mathematical Olympiad 2020 P2

Tags: recurrence relation, Spain



Consider the succession of integers $\{f(n)\}_{n=1}^{\infty}$ defined as: $\bullet$ $f(1) = 1$. $\bullet$ $f(n) = f(n/2)$ if $n$ is even. $\bullet$ If $n > 1$ odd and $f(n-1)$ odd, then $f(n) = f(n-1)-1$. $\bullet$ If $n > 1$ odd and $f(n-1)$ even, then $f(n) = f(n-1)+1$. a) Compute $f(2^{2020}-1)$. b) Prove that $\{f(n)\}_{n=1}^{\infty}$ is not periodical, that is, there do not exist positive integers $t$ and $n_0$ such that $f(n+t) = f(n)$ for all $n \geq n_0$.