Romanian Mathematical Olympiad

a) Since $f(0) > 0$ and $f$ is strictly increasing, it follows that $f(n) > n$, for all $n \in \mathbb{N}$. Consider the sequence of non-negative integers $(n_k)_{k \in \mathbb{N}}$, defined by $n_0 = 0$ and $n_k = f(n_{k-1})$, $k \in \mathbb{N}^*$. The properties of $f$ imply that the sequence is strictly increasing. We define the decreasing sequence $(y_n)_{n \in \mathbb{N}}$, by $y_n = 2^{-k}$, for all $n$ with $n_k \le n < n_{k+1}$, $k \in \mathbb{N}$, obviously convergent to $0$.

It suffices to prove that $y_n \le 2y_{f(n)}$, $n \in \mathbb{N}$, for $n_k \le n < n_{k+1}$, $k \in \mathbb{N}$. Since $f$ strictly increasing, $n_{k+1} = f(n_k) \le f(n) < f(n_{k+1}) = n_{k+2}$, hence $y_{f(n)} = 2^{-k-1} = y_n/2$.

b) Obviously, $x_n \ge 0$, for all $n \in \mathbb{N}$. Using the previously defined sequence $(n_k)$, we define the decreasing sequence of positive reals $(z_k)_{k \in \mathbb{N}}$, as follows: $z_0 = x_1$ and $z_k = \max(x_{n_k}, z_{k-1}/2)$, $k \in \mathbb{N}^*$. The monotony of this sequence follows inductively. Moreover, $(z_k)_{k \in \mathbb{N}}$ converges to $0$: if $z_k = x_{n_k}$, for infinitely many $k$'s, then $z_k \to 0$ because it is decreasing and $x_n \to 0$; if $z_k = x_{n_k}$, only for finitely many $k$'s, then $z_k = z_{k-1}/2$ from some $k$ onwards, and again, $z_k \to 0$.

Finally, we define the sequence $(y_n)_{n \in \mathbb{N}}$ by $y_n = z_k$, $n_k \le n < n_{k+1}$, $k \in \mathbb{N}$. Clearly, the sequence decreases to $0$. In order to prove the inequalities $x_n \le y_n \le 2y_{f(n)}$, $n \in \mathbb{N}$, it suffices to check them for $n_k \le n < n_{k+1}$, $k \in \mathbb{N}$. Obviously, $x_n \le x_{n_k} \le z_k = y_n$. On the other hand, $n_{k+1} = f(n_k) \le f(n) < f(n_{k+1}) = n_{k+2}$, since $f$ is strictly increasing, hence $y_{f(n)} = z_{k+1} \ge z_k/2 = y_n/2$.