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

  • $\begingroup$ Thank you very much! I guess it takes not only intuition, but also trial and error with specific examples! $\endgroup$ – AndrewC Mar 9 '18 at 16:49
  • $\begingroup$ Indeed, and also thinking about the lack of generality in the toy examples you use. Here I used $\frac{1}{(n+1)^2}$ which decreases very quickly but you could have had a slower sequence like $\{\frac{1}{1}, \frac{1}{1}, \frac{1}{1}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{3}, \frac{1}{3}, \frac{1}{3}, \ldots\}$. I also used a simple $f$ but you could have had something which increases faster $f(n)=2n$ or something. $\endgroup$ – TSF Mar 11 '18 at 23:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.