Is every decaying sequence dominated by a convex decaying sequence? Let $\{\psi(n)\}_{n\geqslant 0}$ be a sequence of positive real numbers tending to $0$ as $n \to \infty$. Is there a convex sequence $\{\varphi(n)\}_{n\geqslant 0}$, tending to $0$ as $n \to \infty$ such that $\varphi(n) \geqslant \psi(n)$ for all sufficiently large $n$?
A sequence $a_n$ is convex if  $a_{n+1} + a_{n-1} - 2a_n \ge 0$ for all $n \ge 1$.
I feel this is possible, I've tried to construct a convex sequence greedily, but I can't quite get my finger on it. I would be happy to see an answer in either direction to this question. It came up while trying to solve another problem, but it seems interesting on its own as well.
 A: Yes, that is always possible. One can find a convex sequence $(\phi(n))_n$ which decreases to zero and satisfies $\phi(n) \ge \psi(n)$ for all indices $n$.
To simplify the notation a bit I will assume that the sequence indices start at $n=1$. A convergent sequence is bounded, so without loss of generality we can also assume that $0 \le \psi(n) \le 1/2$ for all $n \ge 1$.
Since $\psi(n)$ converges to zero, we can find a sequence of indices
$$
 1 = n_1 < n_2 < n_3 < \cdots
$$
with the following properties:

*

*$n_{k+1} > 2 n_k$ for all $k$.

*$0 \le \psi(n) \le \frac{1}{2^k}$ for $n \ge n_k$, $k=1, 2, 3, \ldots$.

Now define the “convex majorant” $(\phi(n))_{n \ge 1}$ by setting $\phi(n_k) = \frac{1}{2^{k-1}}$ for $k=1, 2, 3, \ldots$, and linear interpolation between these values on each interval $[n_k, n_{k+1}]$.
It follows immediately from that definition that $\phi(n)$ is (strictly) decreasing and converges to zero. Also, for $n_k \le n \le n_{k+1}$,
$$
\psi(n) \le \frac{1}{2^k} = \phi(n_{k+1}) \le \phi(n) \,.
$$
It remains to show that $\phi$ is convex, and this is where the condition $n_{k+1} > 2 n_k$ comes into play:
$$
 0 < n_k  < n_{k+1} - n_k < 2 n_{k+1}
$$
implies
$$
 -\frac{1}{2^k n_k} < -\frac{1}{2^k(n_{k+1} - n_k )} < - \frac{1}{2^{k+1}n_{k+1}}
$$
so that the slopes of $\phi$ on the interval $[n_k, n_{k+1}]$
$$
 m_k = \frac{\phi(n_{k+1})- \phi(n_k)}{n_{k+1} - n_k} = -\frac{1}{2^k(n_{k+1} - n_k )}
$$
are increasing. This completes the proof.
