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 integer $a_1,a_2,\cdots,a_m$, where $$H(n)=\sum_{k=1}^{n}\frac{1}{k}.$$
Problem
Source: Mar 20, 2018
Tags: inequalities, algebra, China TST
28.03.2018 04:33
Because of the negligence of the proposer, it became quite simple. It should be a bit harder if $C$ is given.
29.03.2018 21:30
Well,actually I really want a detailed proof of this problem.
30.03.2018 00:13
Maybe it should be: "Find the best constant $C>0$"?
31.03.2018 13:38
It's well known that $H(n)\leq \log_2 (n+1)$ for all $n\in \mathbb{Z}^+$. So, it's enough to show that there exists positive constant $C$ that $$\log_2(\prod_{i=1}^{n}{x_i}) \leq C\sqrt{\sum_{i=1}^{n}{i(x_i-1)}}$$for all positive integers $n$ and $x_1,x_2,...,x_n\geq 2$. By Hölder's, we have $$\left( \sum_{i=1}^{n}{i(x_i-1)}\right)^5\sum_{i=1}^{n}{\frac{1}{i^2(x_i-1)^2}}\geq \left( \sum_{i=1}^{n}{\sqrt{i(x_i-1)}}\right)^6.$$Note that $\sum_{i=1}^{n}{\frac{1}{i^2(x_i-1)^2}} \leq \frac{\pi^2}{6} =\sum_{i=1}^{\infty}{\frac{1}{i^2}}$. So, there exists positive constants $c_0$ and $c_1$ that $$\sum_{i=1}^{n}{i(x_i-1)} \geq c_0\left( \sum_{i=1}^{n}{\sqrt{i(x_i-1)}}\right)^{\frac{6}{5}}\implies C\sqrt{\sum_{i=1}^{n}{i(x_i-1)}} \geq Cc_1\left( \sum_{i=1}^{n}{\sqrt{i(x_i-1)}}\right)^{\frac{3}{5}}.$$We also have (since the increasing of $f(x)=x^{\frac{3}{5}}$ when $x\geq 1$) $$\left( \sum_{i=1}^{n}{\sqrt{i(x_i-1)}}\right)^{\frac{3}{5}}\geq \frac{1}{n}\sum_{i=1}^{n}{\left( \sqrt{i(x_i-1)}\right)^{\frac{3}{5}}}.$$So, we want to show that there exists such $C$ that $$2^{\frac{Cc_1}{n}}\prod_{i=1}^{n}{2^{(i(x_i-1))^{\frac{3}{10}}}}\geq \prod_{i=1}^{n}{x_i}.$$In other words, it's enough to show that there exists positive constant $D$ that $$D>\prod_{i=1}^{n}{S_i}$$where $S_i=\frac{2x_i}{2^{(i(x_i-1))^{\frac{3}{10}}}}$ for all $i=1,2,,...,n$. There exists positive integer $N$ that: 1. For $1\leq i\leq N$ (if exists), there exists positive constant $d_i$ that $S_i\leq d_i$ for all $x_i\geq 2$, and 2. For $n\geq i>N$ (if exists), we've $$S_i =\frac{2x_i}{2^{(i(x_i-1))^{\frac{3}{10}}}} \leq \frac{2x_i}{2^{(N(x_i-1))^{\frac{3}{10}}}} <1$$for all $x_i\geq 2$ (WolframAlpha told me $N=1000$ is enough lol) Hence, combining two cases, we can choose $D=\prod_{i=1}^{N}{d_i}$ and finish the problem.
31.03.2018 20:08
smy2012 wrote: Because of the negligence of the proposer, it became quite simple. @ThE-dArK-lOrD I think there's something easier. Especially that high school students don't have to know this $\frac{\pi^2}{6} =\sum_{i=1}^{\infty}{\frac{1}{i^2}}$ or this $H(n)\leq \log_2 (n+1)$
31.03.2018 22:38
Oh, yes, I just realize we don't have to use Hölder and the known fact about $\frac{\pi^2}{6}$. Just note that we've $$C\sqrt{\sum_{i=1}^{n}{i(x_i-1)}} \geq \frac{C}{n}\sum_{i=1}^{n}{\sqrt{i(x_i-1)}}.$$So, it's enough to show that there exists positive constant $D$ that $$D>\prod_{i=1}^{n}{S_i}$$where $S_i=\frac{2x_i}{2^{\sqrt{i(x_i-1)}}}$ for all $i=1,2,...,n$. The rest of the solution proceed easily with the same method as in #7.
09.03.2019 15:38
Here is a simpler solution that gives a concrete value $C$. I claim that $C=2\sqrt{e}$ works. We just need the following machinery: Estimate 1: $H(n)\le 1+\text{ln}(n)$ Proof: $H(n)=1+\sum_{i=2}^{n}\frac{1}{i} \le 1+\sum_{i=2}^{n}\int_{i-1}^{i} \frac{1}{x} ~\text{d}x=1+\text{ln}(n)$ Estimate 2: $n!\ge (\frac{n}{e})^n$ Proof: $\text{ln}{n!}=\sum_{i=2}^{n} \text{ln}(i)\ge \sum_{i=2}^{n}\int_{i-1}^{i}\text{ln}{x}~\text{d}x=n(\text{ln}(n)-1)=\text{ln}((\frac{n}{e})^n)$ Now AM-GM, along with the simple observation that $e^x=(e^{\frac{x}{2}})^2\ge (1+\frac{x}{2})^2$, kills the problem: $$4e(\sum_{i=1}^{m}ia_i)\ge 4e\cdot m\cdot \sqrt[m]{m!}\cdot \sqrt[m]{\prod_{i=1}^{m}a_i}\ge 4m^2\cdot \sqrt[m]{\prod_{i=1}^{m}a_i}\ge 4m^2 \left(\frac{\text{ln}(\prod_{i=1}^{m}a_i)}{2m}+1\right)^2>(\text{ln}(\prod_{i=1}^{m}a_i)+m)^2=[\sum_{i=1}^{m}(\text{ln}(a_i)+1)]^2\ge [\sum_{i=1}^{m}H(a_i)]^2.$$
17.02.2022 07:18
We may assume $a_1,a_2,...,a_m$ is non-decreasing, as this minimizes RHS and LHS stays constant. Let $k=a_1$ for simplicity. For each integer $i$ between 1 and $k$, define $x_i$ to be the amount of integers in $a_1,a_2,...,a_m$ that are at least $i$. Note that for the left hand side, each fraction $\frac{1}{i}$ ocurrs $x_i$ times, therefore LHS is $\sum_{i=1}^k \frac{x_i}{i}$. For the RHS, we want to write $\sum_{i=1}^m ia_i$ in terms of the $x_i$. Express each $a_i$ as $1+1+1+...+1$, where 1 occurs $i$ times. Stick the first one times $i$ in box 1, the second one times $i$ in box 2, etc. Repeating this process, because the sequence is non-increasing if we add up box $j$ for $j$ between $1$ and $k$, we get $\frac{x_j(x_j+1)}{2}$, because we received $i$ from each of the $a_i\geq{}j$, which will be the first $x_j$ of the $a_i$. Therefore, RHS is $\sqrt{\sum_{i=1}^k \frac{x_i(x_i+1)}{2}}$. By CS, we have that: $$LHS=\sum_{i=1}^k \frac{x_i}{i} \leq{}\sqrt{(\sum_{i=1}^k \frac{1}{i^2})(\sum_{i=1}^k x_i^2)}<\sqrt{\frac{\pi^2}{3}}\sqrt{\sum_{i=1}^m ia_i}$$
16.04.2022 08:36
Similar to huricane's solution.