# How prove this inequality $H(a_1)+H(a_2)+\cdots+H(a_m)\leq C\sqrt{\sum_{i=1}^{m}i a_i}$

Prove that: There exists a constant $C>0$ such that $$H(a_1)+H(a_2)+\cdots+H(a_m)\leq C\sqrt{\sum_{i=1}^{m}i a_i}$$ holds for arbitrary positive integer $m$ and any $m$ positive integers $a_1,a_2,\cdots,a_m$, where $H(n)=\sum_{k=1}^{n}\frac{1}{k}.$

This is 2018 China TST 3 Day 1 Q3. Maybe it is from some paper. The reason is that in the past, the Chinese training team selected most of the questions from articles.

• Odd that the left side is symmetric in the $a_i$ while the right side is not. Mar 27, 2018 at 15:10

In view of the rearrangement inequality, it suffices to check the inequality when $(a_i)$ is decreasing, i.e., $a_1 \geq a_2 \geq \cdots \geq a_m$. Also, it is no harm to introduce $a_{m+1} = 0$. Then

$$\sum_{i=1}^{m} H(a_i) = \sum_{i=1}^{m} \sum_{k=i}^{m} \left( H(a_k) - H(a_{k+1}) \right) = \sum_{k=1}^{m} k \left( H(a_k) - H(a_{k+1}) \right)$$

and likewise

$$\sum_{i=1}^{m} i a_i = \sum_{i=1}^{m} \sum_{k=i}^{m} i (a_k - a_{k+1}) = \sum_{k=1}^{m} \frac{k(k+1)}{2} (a_k - a_{k+1}).$$

Now we invoke the following simple lemma:

Lemma. If $0 \leq a < b$ are integers, then $$\frac{H(b) - H(a)}{\sqrt{b-a}} \leq \sqrt{\frac{1}{a+\frac{1}{2}} - \frac{1}{b+\frac{1}{2}}}$$

Before proving this lemma, let us see how this implies the desired inequality. Applying the Cauchy-Schwarz inequality and the lemma above, we obtain

\begin{align*} \sum_{i=1}^{m} H(a_i) &\leq \left( \sum_{k=1}^{m} \frac{2\left( H(a_k) - H(a_{k+1}) \right)^2}{a_k - a_{k+1}} \mathbf{1}_{\{a_k > a_{k+1} \}} \right)^{1/2} \left( \sum_{k=1}^{m} \frac{k^2}{2} (a_k - a_{k+1}) \right)^{1/2} \\ &\leq \left( 2 \sum_{k=1}^{m-1} \left( \frac{1}{a_{k+1}+\frac{1}{2}} - \frac{1}{a_k+\frac{1}{2}} \right) \right)^{1/2} \left( \sum_{i=1}^{m} i a_i \right)^{1/2} \\ &\leq 2 \left( \sum_{i=1}^{m} i a_i \right)^{1/2}. \end{align*}

Therefore the claim is true with $C = 2$.

Proof of Lemma. Notice that for $x \geq 1$,

$$\int_{x-\frac{1}{2}}^{x+\frac{1}{2}} \frac{dt}{t} = \int_{x}^{\infty} \left( \frac{1}{t-\frac{1}{2}} - \frac{1}{t+\frac{1}{2}} \right) \, dt = \int_{x}^{\infty} \frac{4 dt}{4t^2-1} \geq \int_{x}^{\infty} \frac{dt}{t^2} = \frac{1}{x}.$$

(Alternatively, this is the result of the convexity of $\frac{1}{x}$. Indeed, the tangent line $\frac{1}{x} - \frac{1}{x^2}(t-x)$ at $x$ lies below $\frac{1}{t}$, and integrating both sides from $x-\frac{1}{2}$ to $x+\frac{1}{2}$ gives the inequality above.) Then by Cauchy-Schwarz inequality,

\begin{align*} H(b) - H(a) &= \sum_{k=a+1}^{b} \frac{1}{k} \leq \int_{a+\frac{1}{2}}^{b+\frac{1}{2}} \frac{dx}{x} \\ &\leq \left( \int_{a+\frac{1}{2}}^{b+\frac{1}{2}} \frac{dx}{x^2} \right)^{1/2}\left( \int_{a+\frac{1}{2}}^{b+\frac{1}{2}} dx \right)^{1/2} \\ &= \Bigg( \frac{1}{a+\frac{1}{2}}-\frac{1}{b+\frac{1}{2}} \Bigg)^{1/2} \sqrt{b-a}. \end{align*}

• How to find this nice answer! Thanks Mar 29, 2018 at 14:54
• @functionsug, Thank you! The idea of utilizing the summation by parts was rather a luck. Once this is done, the rest was simply to apply CS-inequality and see what happens. The resulting sum $$\sum_{k=1}^{m} \left( \frac{H(a_k) - H(a_{k+1})}{a_k - a_{k+1}} \right)^2 (a_k - a_{k+1})$$ reminded me of a Riemann sum for the integral $\int_{1}^{a_1} \frac{1}{x^2} \, dx$, which led me to devise the lemma. Mar 29, 2018 at 15:01
• Nice! and I have other question,the $C=2$ is best? Mar 29, 2018 at 15:14
• @functionsug, That is an interesting question. I suspect otherwise, but I have no good idea of achieving a sharp bound. Mar 29, 2018 at 15:33
• oh,No,I have found have some wrong,$k(a+b+1-k)\le\dfrac{(a+b+1)^2}{4}$,not $\ge$. May 7, 2018 at 10:38

Sketch of an almost proof since I'm on my phone.

$H(a_i)<\ln(a_i+1) < ca_i^{1/2}$ for some $c>0$.

Therefore $\sum H(a_i) <\sum ca_i^{1/2}$.

Since $\frac1{m}\sum a_i^{1/2} \le \sqrt{\frac1{m}\sum a_i}$ by the power mean inequality, $\sum a_i^{1/2} \le \sqrt{m\sum a_i}$ so that $\sum H(a_i) <c\sqrt{m\sum a_i}$.

So if we can show that $m\sum a_i < b \sum ia_i$ for some $b$ we are done.

This is true if we can choose $b=m+1$ but not if $b$ is independent of $m$. For example, choose $a_1$ large ($m^2$) and all the others small (1). The left side is about $m^3$ and the right side is about $bm^2$.

I don't know where to go from here so I'll stop.

As Sangchul Lee pointed out in his answer, by the rearrangement inequality we may assume $$a_1\ge a_2\ge\dots\ge a_m$$. Also, for any positive integer $$n$$, let $$S(n)$$ denote the sum of the integers from 1 to $$n$$, so $$S(n)=\frac{n(n+1)}{2}$$.

For each positive integer $$j$$, let $$n_j$$ denote the number of $$i\in\{1,\dots,m\}$$ such that $$a_i\ge j$$. Let $$N$$ denote the largest positive integer such that $$n_N\ne0$$. The desired inequality can then be rewritten as $$\sum_{j=1}^{N}\frac{n_j}{j}\le C\sqrt{\sum_{j=1}^{N}S(n_j)}.$$ It is equivalent to show that there is some constant $$C'$$ such that $$\sum_{j=1}^{N}\frac{n_j}{j}\le C'\sqrt{\sum_{j=1}^{N}n_j^2}.$$

We expect the sum on the right hand side to be dominated by the $$n_j$$ that are close to $$n_1$$ (since $$n_1$$ is the largest among all $$n_j$$). To this end, it suffices to find values for "cutoff factors" $$\lambda_j$$ for each positive integer $$j>1$$ such that the above inequality holds even if, on the left hand side, we approximate $$n_j$$ by $$n_1$$ if $$n_j>\lambda_j n_1$$ and $$\lambda_j$$ otherwise, and on the right hand side, we approximate $$n_j$$ by $$\lambda_j n_1$$ if $$n_j<\lambda_jn_1$$ and by 0 otherwise. That is, it suffices to find $$C''$$ and $$\lambda_j$$ such that, if $$G$$ denotes the set of positive integers such that $$n_j>\lambda_jn_1\Leftrightarrow j\in G$$, then (letting $$\lambda_1:=1$$ and $$1\in G$$ for convenience of notation) $$\left(\sum_{j\in G,j\le N}\frac{n_1}{j}\right)+\left(\sum_{j\notin G,j\le N}\frac{\lambda_j n_1}{j}\right)\le C''\sqrt{\sum_{j\in G,j\le N}(\lambda_jn_1)^2}.$$ always holds. Factoring out $$n_1$$, we want $$\left(\sum_{j\in G,j\le N}\frac{1}{j}\right)+\left(\sum_{j\notin G,j\le N}\frac{\lambda_j}{j}\right)\le C''\sqrt{\sum_{j\in G,j\le N}\lambda_j^2}.$$

It suffices to find such $$\lambda_j$$ and constants $$C''_1, C''_2$$ such that $$\sum_{j\in G,j\le N}\frac{1}{j}\le C''_1\sqrt{\sum_{j\in G,j\le N}\lambda_j^2},\quad\sum_{j\notin G,j\le N}\frac{\lambda_j}{j}\le C''_2\sqrt{\sum_{j\in G,j\le N}\lambda_j^2}.$$ For the second inequality, since $$1\in G$$ and $$\lambda_1=1$$, it suffices to pick $$\lambda_j$$ such that $$\sum_{j=1}^{\infty}\frac{\lambda_j}{j}$$ converges.

For the first inequality, we want $$\left(\sum_{j\in G,j\le N}\frac{1}{j}\right)^2\le \left(C''_1\right)^2\sum_{j\in G,j\le N}\lambda_j^2.$$ We can bound the left hand side above by $$\left(\sum_{j\in G,j\le N}\frac{1}{j}\right)^2\le H\left(\left\lvert G\right\rvert\right)\sum_{j\in G,j\le N}\frac{1}{j}\le\log\left(\left\lvert G\right\rvert+1\right)\sum_{j\in G,j\le N}\frac{1}{j}.$$ It is not hard to show that setting $$\lambda_j=\sqrt{\frac{\log(j)}{j}}$$ makes this inequality hold (the worst case is when the elements of $$G$$ are $$\{1,\dots,\lvert G\rvert\}$$), and also satisfies that $$\sum_{j=1}^{\infty}\frac{\lambda_j}{j}$$ converges.