# Proof by induction -inequality

Prove that $1 + \frac{1}{2}+ \frac{1}{3} + .... + 1/n < 2\sqrt{n}$ for $n \ge1$

Here's my attempt:

Base case: $P(1): \frac{1}{1} \le 2\sqrt{1} = 1 \le 2$ (Base case true)

Assume $n = k$ for $k \ge1$ such that $1 + \frac{1}{2}+ \frac{1}{3} + .... + \frac{1}{k} < 2\sqrt{k}$

INDUCTION HYPOTHESIS: $1 + \frac{1}{2}+ \frac{1}{3} + .... + \frac{1}{k} < 2\sqrt{k}$

Now for P(k+1), we must show that $1 + \frac{1}{2}+ \frac{1}{3} + .... + \frac{1}{k+1}$ $< 2\sqrt{k+1}$

$1 + \frac{1}{2}+ \frac{1}{3} + .... + \frac{1}{k} +\frac{1}{k+1}$ $< 2\sqrt{k+1}$

By our induction hypothesis: $2\sqrt{k} + \frac{1}{k+1} <2\sqrt{k+1}$

Now, I add $2\sqrt{k}$ to the right side. $2\sqrt{k} + \frac{1}{k+1} <2\sqrt{k+1} + 2\sqrt{k}$ (the inequality is still true)

Then, substract $2\sqrt{k}$ from both sides,

Hence, $\frac{1}{k+1} <2\sqrt{k+1}$

QED

Also looking forward to see other ways to complete this induction! Thanks!

• This is scircular, you already assumed your conclusion in the begining. – Zelos Malum Dec 1 '15 at 5:38
• When I read your proof again, you seem to try to go from bottom up and you only wrote down the "deriving process". However, when you try do derive from conclusion you need to pay attention to the difference between $p\implies q$ and $p\iff q$. For example in your proof even though $2\sqrt{k} + \frac{1}{k+1} <2\sqrt{k+1}\implies 2\sqrt{k} + \frac{1}{k+1} <2\sqrt{k+1} + 2\sqrt{k}$, the converse is not true. – cr001 Dec 1 '15 at 5:59

## 1 Answer

The problem within your proof is that you assume $1 + \frac{1}{2}+ \frac{1}{3} + .... + \frac{1}{k} +\frac{1}{k+1}< 2\sqrt{k+1}$ at the beginning but this is not allowed; you are trying to prove it but you assume it at first.

Another problem is that, when you apply the induction hypothesis, you are saying $A<B,A<C$ hence $B<C$ which is logically incorrect.

To prove it you need to show $${1\over{k+1}}<2\sqrt{k+1}-2\sqrt{k}$$

which comes from

$${1\over{k+1}}={2\over{(k+1)+(k+1)}}<{2\over{\sqrt{k+1}+\sqrt{k}}}=2\sqrt{k+1}-2\sqrt{k}$$

Hence

$$1 + \frac{1}{2}+ \frac{1}{3} + .... + \frac{1}{k} +\frac{1}{k+1}<2\sqrt{k}+{1\over k+1}< 2\sqrt{k+1}$$

• Well done! ... +1 – Mark Viola Dec 1 '15 at 5:50