Let $f:\mathbb{N}_{\geq 0} \to \mathbb{N}_{\geq 1}$ be a strictly increasing function and $(x_n)_{n \geq 0}$ a decreasing sequence such that $x_n \to 0$.
Construct a decreasing sequence $(y_n)_{n \geq 0}$ such that $y_n \to 0$ and $$x_n \leq y_n \leq 2y_{f(n)}, \: \forall n \in \mathbb{N}_{\geq 0}$$
Construction problems like this one always put me in trouble and sometimes, I don't even know how to approach them. That function $f$ is so generally defined that I don't know what to do with it. All I got is the immediate fact that $f(n) \geq n+1$ and this means that $x_n \leq y_n \leq 2 y_{n+1}$ so we should construct $(y_n)$ such that $y_{n+1}$ is between $\frac{y_n}{2}$ and $y_n$.
I would really appreciate an intuitive look upon the solution, that is, a motivation for each step involving the construction of $(y_n).$
Okay I am still working on the explanation and proof here but after playing around with this I think a solution would be the following:
Let $y_0 = x_0$. Then, for $n>0$, define,
$$y_n = \begin{cases}\max\left\{x_n, \frac{y_0}{2}\right\} & \mbox{if}\quad 0<n\leq f(0),\\ \max\left\{x_n, \frac{y_{f(0)}}{2}\right\} & \mbox{if}\quad f(0)<n\leq f^2(0),\\ \max\left\{x_n, \frac{y_{f^2(0)}}{2}\right\} & \mbox{if}\quad f^2(0)<n\leq f^3(0),\\ \ldots\\ \max\left\{x_n, \frac{y_{f^k(0)}}{2}\right\} & \mbox{if}\quad f^{k}(0)<n\leq f^{k+1}(0),\\ \ldots\end{cases}$$
Edit: Proving these things is turning out to be really ugly and brute force but I am sure this is a solution, although without the explanation I know it is essentially useless for you. Sorry for the lack of elegance. Hopefully someone smarter can come up with something nicer.
How I came up with the proposed solution is by letting $x_n=\frac{1}{(n+1)^2}$, $f(n) = n+3$, and just toying with different choices of $y_n$. I came to realize that the important spots in the sequence are when the function $f$ is composed with itself, so in the test case it was $n=0,3,6,9,\ldots$. You can basically keep things constant in these intervals if $x_n$ is decreasing fast enough, and if not you can always just take $y_n=x_n$.
Proof that it is a decreasing sequence:
Let $m,n\in\mathbb{N}_{\geq 1}$ with $m>n$ (since if $n=0$ then $y_m\leq y_n$ trivially since $x_n$ is decreasing). The number $n$ must fall into one of the intervals $]f^k(0),f^{k+1}(0)]$ for some $k\in\mathbb{N}_{\geq 0}$ with the convention that $f^0(0)=0$. Thus, $y_n=\max\{x_n,\frac{y_{f^{k}(0)}}{2}\}$. If $m\in]f^{k}(0),f^{k+1}(0)]$ then we have that $y_m=\max\{x_m,\frac{y_{f^{k}(0)}}{2}\}$.
If $y_m=x_m$ we have $y_m=x_m\leq x_n\leq y_n$. On the other hand, if $y_m=\frac{y_{f^{k}(0)}}{2}$ we have $y_m=\frac{y_{f^{k}(0)}}{2}\leq y_n$.
Now, consider that $m\not\in]f^{k}(0),f^{k+1}(0)]$. Then we have that $m\in]f^{l}(0),f^{l+1}(0)]$ for some $l>k$, i.e. $y_m = \max\{x_m, \frac{y_{f^{l}(0)}}{2}\}$. If $y_m=x_m$ we automatically have $y_m=x_m\leq x_n\leq y_n$ since $x_n$ is decreasing. On the other hand, if $y_m = \frac{y_{f^{l}(0)}}{2}$ we have $y_m = \frac{y_{f^{l}(0)}}{2}\leq y_{f^l(0)}=\max\{x_{f^l(0)},\frac{y_{f^{l-1}(0)}}{2}\}$
okay it's too ugly