Inequality with a sum

Question

I am reading Remarks on a Ramsey theory for trees: Janos Pach, Jozsef Solymosi, Gabor Tardos http://arxiv.org/abs/1107.5301 I am stuck at inequality in proof of Lemma 6.

$n\geq 8$, $k=2\lfloor 3n/\log_2 n \rfloor$, $l = k/2 + 1$ We have

$$\sum_{i=1}^l \frac{l}{2^{m_i}} - n \geq \frac{l^2}{n^{1/3}} - n$$

This inequality should come from fact, that $\sum_i m_i \leq n$ and $2^{-m}$ is a convex function.

---

When I read "convex function" first that came on my mind was Jensen's inequality $\varphi \left( \sum x_i \right) \leq \sum \varphi(x_i)$. But this gives me much weaker result:

$$\sum_{i=1}^l \frac{l}{2^{m_i}} - n \geq \frac{l}{2^n} - n$$

What am I missing? There is everything relevant I hope. If I omitted something important I am sorry.

Answer 1

Another form of Jensen's inequality is that for a convex function $\phi$, we have that $\displaystyle \sum_i \lambda_i \phi(m_i) \geq \phi(\sum_i \lambda_i m_i)$. Take $\displaystyle \lambda_i = \frac{1}{l}$, and that becomes $\displaystyle \sum \frac{1}{l}2^{-m_i} \geq 2^{-\sum_i m_i/l} = 2^{-n/l}$. In other words, $\displaystyle \sum_i \frac{1}{2^{m_i}} \geq \frac{l}{2^{n/l}}$. Since $\displaystyle \frac{n}{l}$ is about $\frac{1}{3}\log n$, so we get that $\displaystyle \sum_i \frac{1}{2^{m_i}} \geq \frac{l}{n^{1/3}}$, which gives the inequality.

Answer 2

We will substitute $\sum_{i=1}^l m_i$ with sum of something bigger ($2^{-m}$ is decreasing) than it's arithmetic mean and Jensen will do the rest. As $l=3n/\log n$, the important part goes:

$$\sum_{i=1}^l 2^{-m_i} \geq \sum_{i=1}^l 2^{-n/l} = l 2^{-n/l} = l 2^{-n\log n/(3n)} = l2^{-\log n/3} = ln^{-1/3}$$

I should practice these computations more. If you find something wrong please let me know.