# Proving a summation inequality with induction

The exact question:

Prove:

$\displaystyle\sum_{k=1}^n \frac{1}{\sqrt{k}}\gt2(\sqrt{n+1}-1)$

I have looked at similar problems but still don't understand how to prove this inequality by induction. So far I have this:

Induction basis:

Let n=1

$\displaystyle\sum_{k=1}^n \frac{1}{\sqrt{k}} = \frac{1}{\sqrt{1}} = 1 > 2(\sqrt{1+1}-1) = ~.828$

$1>.828$

So it proves the inequality true when n=1.

Now i really don't know how to continue even with all the examples i have browsed through. One of them i came across showed that the induction hypothesis should let P(n) equal the equation above and do something with P(n+1). I am not looking for the answer I just need help on how to continue with the problem. What other steps are necessary for me to complete this proof by induction.

## 4 Answers

Inductive steps: Assume the inequality is true for $n=N$.

so $\displaystyle\sum_{k=1}^N \frac{1}{\sqrt{k}}\gt2(\sqrt{N+1}-1)$

Now if $n=N+1$,

$\displaystyle\sum_{k=1}^{N+1} \frac{1}{\sqrt{k}} =\displaystyle\sum_{k=1}^N \frac{1}{\sqrt{k}}+ \frac{1}{\sqrt{N+1}} >2(\sqrt{N+1}-1) + \frac{1}{\sqrt{N+1}}$

... (I left the part here for you to figure out)

$>2(\sqrt{N+2}-1)$

Hint: you want to prove that $\frac{1}{\sqrt{n}} \geq 2(\sqrt{N+2}-\sqrt{N+1})$ by multiplying by the conjugate term

Use this fact $$\sqrt{n+1} - \sqrt{n} = {1\over \sqrt{n} + \sqrt{n+1}}.$$ Now produce a bound and sum a telescoping sum.

First you have to establish your statement of $P(n)$. Here the statement should be:

$$P(n) \,\, : \,\, \displaystyle\sum_{k=1}^n \frac{1}{\sqrt{k}}\gt2(\sqrt{n+1}-1)$$

Now you go into the induction part. Equipped with the hypothesis that $P(n)$ is true, you need to prove that $P(n+1)$ is also true.

$$P(n+1) \,\, : \,\, \displaystyle\sum_{k=1}^{n+1} \frac{1}{\sqrt{k}}\gt2(\sqrt{(n+1)+1}-1)$$

• Stupid question, could i just let n be a number and prove it that way? or does it go deeper than that. – user2494817 Nov 6 '15 at 2:19
• No you have to prove that it is true for ALL values of $n$ which are greater than or equal to your initial value. Here you choose your initial value $n=1$. So you have to prove that it is true for ALL $n = 1, 2, 3, 4, \cdots$ – corindo Nov 6 '15 at 2:22
• ok, that is what i assumed, thanks! – user2494817 Nov 6 '15 at 2:24

The induction step assumes $$\sum_{k = 1}^n \frac{1}{\sqrt{k}} > 2\sqrt{n + 1} - 2.$$ Using it, it follows that \begin{align} & \sum_{k = 1}^{n + 1} \frac{1}{\sqrt{k}} \\ = & \sum_{k = 1}^n \frac{1}{\sqrt{k}} + \frac{1}{\sqrt{n + 1}} \\ > &2\sqrt{n + 1} - 2 + \frac{1}{\sqrt{n + 1}} \\ = & 2 \sqrt{n + 2} - 2 + \left[2(\sqrt{n + 1} - \sqrt{n + 2}) + \frac{1}{\sqrt{n + 1}}\right] \\ = & 2 \sqrt{n + 2} - 2 + \left[\frac{1}{\sqrt{n + 1}} - 2\frac{1}{\sqrt{n + 2} + \sqrt{n + 1}}\right] \quad \text{multiply conjugate}\\ > & 2 \sqrt{n + 2} - 2 + \left[\frac{1}{\sqrt{n + 1}} - 2\frac{1}{2\sqrt{n + 1}}\right] \\ = & 2 \sqrt{(n + 1) + 1} - 2, \end{align} finishes the induction step.