8
$\begingroup$

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.

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

3 Answers 3

4
+50
$\begingroup$

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*}

$\endgroup$
8
  • $\begingroup$ How to find this nice answer! Thanks $\endgroup$
    – math110
    Mar 29, 2018 at 14:54
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 29, 2018 at 15:01
  • $\begingroup$ Nice! and I have other question,the $C=2$ is best? $\endgroup$
    – math110
    Mar 29, 2018 at 15:14
  • $\begingroup$ @functionsug, That is an interesting question. I suspect otherwise, but I have no good idea of achieving a sharp bound. $\endgroup$ Mar 29, 2018 at 15:33
  • $\begingroup$ oh,No,I have found have some wrong,$k(a+b+1-k)\le\dfrac{(a+b+1)^2}{4}$,not $\ge $. $\endgroup$
    – math110
    May 7, 2018 at 10:38
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.