# Prove $(\sum_{n=1}^k n)\cdot(\sum_{n=1}^k \frac1n) \geq k^2$ for $k\in\mathbb N$

$$\left(\sum_{n=1}^k n\right)\cdot\left(\sum_{n=1}^k \frac1n\right) \geq k^2 \qquad \text{for} \qquad k\in\mathbb N.$$

By induction, I've checked the base and it gives $$1=1$$. Now I'm stuck at the induction steps. Assume it is true for some natural number $$m$$, then we have that \begin{align*} \left(\sum_{n=1}^{m+1} n\right)\cdot\left(\sum_{n=1}^{m+1} \frac1n\right) &=\left(\sum_{n=1}^m n\right)\cdot\left(\sum_{n=1}^m \frac1n\right) + (k+1)\sum_{n=1}^m \left(\frac1n\right) + \frac1{k+1}\sum_{n=1}^m\big(n\big)+1\\ &\ge k^2 + k+1 + \frac1{k+1}\cdot\frac{k(k+1)}2 +1\\ &=k^2+k+\frac k2+2 \end{align*} I thought I was heading in the right direction but this doesn't seem to be bigger than $$k^2+2k+1$$ so I'm not sure how to proceed. Thank you.

First of all, your $$k$$ and $$m$$ are the same. To make things clearer, I use the notation $$k$$ instead of $$m$$. By induction, we assume that $$\left(\sum\limits_{n=1}^k n\right)\cdot\left(\sum\limits_{n=1}^k \frac1n\right) \geq k^2,$$ and we're going to show that $$\left(\sum\limits_{n=1}^{k+1} n\right)\cdot\left(\sum\limits_{n=1}^{k+1} \frac1n\right) \geq (k+1)^2.\tag{*}$$ You have shown that \begin{align*} \left(\sum\limits_{n=1}^{k+1} n\right)\cdot\left(\sum\limits_{n=1}^{k+1} \frac1n\right)&\geq k^2+(k+1)\sum_{n=1}^k\frac1n+\frac1{k+1}\sum_{n=1}^kn+1\\ &=k^2+\frac k2+1+(k+1)\sum_{n=1}^k\frac1n. \end{align*} As a result, to show $$(*)$$, it suffices to prove that $$(k+1)\sum_{n=1}^k\frac1n\geq\frac{3k}{2},$$ which is equivalent to $$\sum_{n=1}^k\frac1n\geq\frac{3k}{2(k+1)}.\tag{**}$$ Now, we can use another induction to show $$(**)$$. Clearly $$(**)$$ holds for $$k=1$$. Assume that $$(**)$$ holds for $$k$$, we need to prove $$\sum_{n=1}^{k+1}\frac1n\geq\frac{3(k+1)}{2(k+2)}.\tag{1}$$ Indeed, we have $$\sum_{n=1}^{k+1}\frac1n=\sum_{n=1}^{k}\frac1n+\frac1{k+1}\geq \frac{3k}{2(k+1)}+\frac1{k+1}=\frac{3k+2}{2(k+1)}.$$ So, it suffices to show that $$\frac{3k+2}{2(k+1)}\geq\frac{3(k+1)}{2(k+2)}$$, which is equivalent to $$(3k+2)(k+2)\geq3(k+1)^2$$. We have simply $$(3k+2)(k+2)\geq3(k+1)^2=2k+1>0.$$ Therefore $$(1)$$ holds and hence $$(**)$$ holds for all $$k$$. This completes the proof.

Quicker proof. Your desired inequality is a direct consequence of Cauchy–Schwarz inequality.

Quicker proof of $$(**)$$ from comments: $$(**)$$ holds clearly for $$k=1$$. And for $$k\geq 2$$, note that $$\sum_{n=1}^k\frac1n\geq1+\frac12=\frac32=\frac{3(k+1)}{2(k+1)}>\frac{3k}{2(k+1)}.$$

• Brilliant! Thank you and I'll check out how to use cauchy schwarz. Commented Dec 24, 2023 at 8:13
• @MrFreitag You're welcome. I'm very glad to be helpful! Just take $u_i=\sqrt i$ and $v_i=1/\sqrt i$ in the linked version of Cauchy–Schwarz inequality.
– Feng
Commented Dec 24, 2023 at 8:15
• More directly, for $k \geq 2$, $\sum 1/n \geq 1 + 1/2 > \frac{3k}{2k+2}$. So check $k = 1$ and we are done. Commented Dec 24, 2023 at 8:21