Kvant Math Problem 1171
Let
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m31s
Source on kvant.digital
Problem
Let the sum $1+\dfrac12+\dfrac13+\ldots+\dfrac1n$ be denoted by $h_n$. Prove (for each natural number $n$) the inequality $$\dfrac1{h_1^2}+\dfrac1{2h_2^2}+\dfrac1{3h_3^2}+\ldots+\dfrac1{nh_n^2}\lt 2.$$.
L. D. Kurlandchik
Exploration
Let
$$S_n=\sum_{k=1}^{n}\frac1{k h_k^2}.$$
The inequality to prove is $S_n<2$ for every $n$.
First compute a few terms:
$$h_1=1,\qquad h_2=\frac32,\qquad h_3=\frac{11}{6}.$$
Hence
$$S_1=1,$$
$$S_2=1+\frac1{2(3/2)^2}=1+\frac29=\frac{11}{9},$$
$$S_3=\frac{11}{9}+\frac1{3(11/6)^2} =\frac{11}{9}+\frac{12}{121}\approx1.322.$$
The sum grows slowly, so a telescoping estimate is plausible.
Since
$$h_k-h_{k-1}=\frac1k,$$
the summand can be rewritten as
$$\frac1{k h_k^2} =\frac{h_k-h_{k-1}}{h_k^2}.$$
A natural comparison is
$$\frac{h_k-h_{k-1}}{h_k^2} \le \frac1{h_{k-1}}-\frac1{h_k},$$
because the right-hand side telescopes. Checking:
$$\frac1{h_{k-1}}-\frac1{h_k} = \frac{h_k-h_{k-1}}{h_{k-1}h_k}.$$
Thus we need
$$\frac1{h_k^2} \le \frac1{h_{k-1}h_k},$$
which is true since $h_k\ge h_{k-1}$.
Summing would give
$$S_n \le \sum_{k=1}^{n} \left(\frac1{h_{k-1}}-\frac1{h_k}\right),$$
but $h_0$ is not defined. The first term must be separated.
For $k\ge2$,
$$\frac1{k h_k^2} \le \frac1{h_{k-1}}-\frac1{h_k}.$$
Then
$$S_n = 1+\sum_{k=2}^{n}\frac1{k h_k^2} \le 1+\sum_{k=2}^{n} \left(\frac1{h_{k-1}}-\frac1{h_k}\right) = 1+\left(1-\frac1{h_n}\right) = 2-\frac1{h_n}.$$
Since $h_n>1$ for every $n\ge2$, this yields $S_n<2$. For $n=1$, $S_1=1<2$.
The only potentially delicate step is the comparison with the telescoping difference.
Problem Understanding
We must prove that for every natural number $n$,
$$\sum_{k=1}^{n}\frac1{k h_k^2}<2,$$
where
$$h_k=1+\frac12+\cdots+\frac1k$$
is the $k$-th harmonic number.
This is a Type B problem, a pure proof.
The core difficulty is to recognize a telescoping quantity related to the factor $1/k=h_k-h_{k-1}$. Once the summand is compared with a telescoping difference of reciprocals of harmonic numbers, the inequality follows.
Proof Architecture
The first claim is that for every $k\ge2$,
$$\frac1{k h_k^2} \le \frac1{h_{k-1}}-\frac1{h_k}.$$
This follows from $h_k-h_{k-1}=1/k$ and the inequality $h_{k-1}\le h_k$.
The second claim is that summing these inequalities from $k=2$ to $n$ produces a telescoping series,
$$\sum_{k=2}^{n} \left(\frac1{h_{k-1}}-\frac1{h_k}\right) = 1-\frac1{h_n}.$$
This is the standard telescoping cancellation.
The final step is to separate the first term of the original sum, apply the previous estimate, and obtain
$$S_n\le 2-\frac1{h_n}<2.$$
The lemma most likely to fail under scrutiny is the first comparison inequality, because it contains the entire nontrivial estimate.
Solution
Define
$$S_n=\sum_{k=1}^{n}\frac1{k h_k^2}.$$
For every $k\ge2$,
$$h_k-h_{k-1}=\frac1k.$$
Hence
$$\frac1{k h_k^2} = \frac{h_k-h_{k-1}}{h_k^2}.$$
Since $h_{k-1}\le h_k$, we have
$$h_{k-1}h_k\le h_k^2,$$
and therefore
$$\frac1{h_k^2} \le \frac1{h_{k-1}h_k}.$$
Multiplying by the positive quantity $h_k-h_{k-1}$ gives
$$\frac{h_k-h_{k-1}}{h_k^2} \le \frac{h_k-h_{k-1}}{h_{k-1}h_k}.$$
Using $h_k-h_{k-1}=1/k$,
$$\frac1{k h_k^2} \le \frac{h_k-h_{k-1}}{h_{k-1}h_k} = \frac1{h_{k-1}}-\frac1{h_k}.$$
Summing this inequality for $k=2,3,\ldots,n$, we obtain
$$\sum_{k=2}^{n}\frac1{k h_k^2} \le \sum_{k=2}^{n} \left(\frac1{h_{k-1}}-\frac1{h_k}\right).$$
The right-hand side telescopes:
$$\sum_{k=2}^{n} \left(\frac1{h_{k-1}}-\frac1{h_k}\right) = \frac1{h_1}-\frac1{h_n} = 1-\frac1{h_n}.$$
Consequently,
$$S_n = \frac1{h_1^2} + \sum_{k=2}^{n}\frac1{k h_k^2} \le 1+\left(1-\frac1{h_n}\right) = 2-\frac1{h_n}.$$
If $n=1$, then $S_1=1<2$.
If $n\ge2$, then $h_n>1$, so
$$2-\frac1{h_n}<2.$$
Thus in all cases
$$\sum_{k=1}^{n}\frac1{k h_k^2}<2.$$
This completes the proof.
∎
Verification of Key Steps
The critical estimate is
$$\frac1{k h_k^2} \le \frac1{h_{k-1}}-\frac1{h_k}.$$
Starting from the right-hand side,
$$\frac1{h_{k-1}}-\frac1{h_k} = \frac{h_k-h_{k-1}}{h_{k-1}h_k} = \frac1{k,h_{k-1}h_k}.$$
Therefore the estimate is equivalent to
$$\frac1{h_k^2} \le \frac1{h_{k-1}h_k},$$
which is exactly the consequence of $h_{k-1}\le h_k$. No hidden assumption is used.
The telescoping step is
$$\sum_{k=2}^{n} \left(\frac1{h_{k-1}}-\frac1{h_k}\right) = \left(\frac1{h_1}-\frac1{h_2}\right) +\left(\frac1{h_2}-\frac1{h_3}\right) +\cdots +\left(\frac1{h_{n-1}}-\frac1{h_n}\right).$$
Every intermediate term cancels, leaving
$$\frac1{h_1}-\frac1{h_n}.$$
A common mistake would be to begin the sum at $k=1$, which would introduce the undefined quantity $h_0$. Separating the first term avoids this issue completely.
The strict inequality at the end requires checking that
$$2-\frac1{h_n}<2.$$
For $n\ge2$,
$$h_n=1+\frac12+\cdots+\frac1n>1,$$
so $1/h_n>0$. For $n=1$, the original sum equals $1$. Thus every value of $n$ is covered.
Alternative Approaches
One may rewrite the summand as
$$\frac1{k h_k^2} = \frac{h_k-h_{k-1}}{h_k^2}$$
and compare it with the integral
$$\int_{h_{k-1}}^{h_k}\frac{dx}{x^2}.$$
Since $x\le h_k$ throughout the interval $[h_{k-1},h_k]$,
$$\int_{h_{k-1}}^{h_k}\frac{dx}{x^2} \ge \frac{h_k-h_{k-1}}{h_k^2} = \frac1{k h_k^2}.$$
Summing over $k\ge2$ gives
$$\sum_{k=2}^{n}\frac1{k h_k^2} \le \int_{1}^{h_n}\frac{dx}{x^2} = 1-\frac1{h_n},$$
and the same conclusion follows.
The telescoping proof is preferable because it stays entirely within elementary algebra and exhibits directly the quantity whose differences dominate the summands.