How to prove $n \ge 2 {\left ( \sum_{k=1}^n \frac{1}{k} \right)}^2$ for all $n \ge 2$?

Question

I'm trying to prove that $$n \ge 2 {\left ( \sum_{k=1}^n \frac{1}{k} \right)}^2$$ for all $n \ge 2$. I try induction on $n$ as follows:

---

My attempt:

The inequality holds for $n=2$. Let it holds for $n$. Our goal is to show that $$2 {\left ( \sum_{k=1}^n \frac{1}{k} \right)}^2+1 \ge 2 {\left ( \sum_{k=1}^{n+1} \frac{1}{k} \right)}^2$$

This is equivalent to $$1 \ge \frac{1}{n+1} \left ( \frac{1}{n+1}+ \sum_{k=1}^n \frac{1}{k} \right) =\frac{1}{(n+1)^2} + \frac{1}{n+1} \sum_{k=1}^n \frac{1}{k}$$

I'm unable to approximate the sum $\sum_{k=1}^n \frac{1}{k}$. Could you please shed me some light on the last step?

Answer 1

Note that the statement itself tells you how to approximate $\sum_{k=1}^{n} \frac{1}{k}$, so with wishful thinking we hope it is sufficient (which need not be the case).

---

Change the statement to showing that $\sqrt{\frac{n}{2}} \geq \sum_{k=1}^{n} \frac{1}{k}$.

Then, the induction step requires us to show that $\sum_{k=1}^{n+1} \frac{1}{k} \leq \sqrt{\frac{n}{2}} + \frac{1}{n+1} \leq \sqrt{ \frac{n+1}{2}}$

Since $\sqrt{ \frac{n+1}{2}} - \sqrt{ \frac{n}{2}} = \frac{\frac{1}{2}}{\sqrt{ \frac{n+1}{2}} + \sqrt{ \frac{n}{2}}} \geq \frac{1}{2*\sqrt{2(n+1)}} \geq \frac{1}{n+1}$ when $n+1 \geq 8$.

So, start the induction at $n= 7$, and check the initial base cases.

Answer 2

We can use that bound for harmonic series

$$\sum_{k=1}^n\frac{1}{k} \leq \ln n + 1$$

therefore

$$\frac{1}{(n+1)^2} + \frac{1}{n+1} \sum_{k=1}^n \frac{1}{k}\le \frac{1}{(n+1)^2} + \frac{\ln n + 1}{n+1} \le 1$$

indeed

$$ \frac{1}{(n+1)^2} + \frac{\ln n + 1}{n+1} \le 1 \iff \frac{1}{n+1} + \ln n + 1 \le n+1 \iff \ln n \le n-\frac{1}{n+1}$$

which is true indeed

$$ \ln (1+(n-1)) \le n-1\le n-\frac{1}{n+1}$$