# Proof by induction

1. Aug 23, 2014

### johann1301

1. The problem statement, all variables and given/known data

Prove this by induction

n
∑(1/√n) > 2(√(n+1) -1)
i=1

3. The attempt at a solution

I have tried for several hours, with no real progress. When i assume that it works for n=k, and then try to prove for n=k+1 i get 2(√(k+2)-1)... i don't know how to partition this expression... can someone point me in the right direction....

2. Aug 23, 2014

### Ray Vickson

Are you absolutely required to use induction? If not, there is a quick proof using elementary calculus (specifically, definite integration).

3. Aug 23, 2014

### johann1301

The task is part of the induction chapter in the textbook.

4. Aug 23, 2014

### Mogarrr

Are you sure that the left-hand side of the inequality is...

$\sum_{k=1}^{n} \frac 1{\sqrt {n}}$, rather than $\sum_{k=1}^{n} \frac 1{\sqrt {k}}$ ?

5. Aug 23, 2014

### johann1301

woops!, i can correct it...

6. Aug 23, 2014

### johann1301

m
∑(1/√n) > 2(√(n+1) -1)
n=1

7. Aug 23, 2014

### johann1301

Again, the problem for me lies in that i can't partition(divide in to a sum) the expression on the right...

8. Aug 23, 2014

### Mogarrr

Um, what is m?

9. Aug 23, 2014

### johann1301

So sorry, I'm not so good at the different placements for the different sum-limits/-startpoints. I first introduced "k" when i assumed that the inequality actually was valid, and then i set n=k+1 and tried to prove it...

This should be right;
n
∑(1/√i) > 2(√(n+1) -1)
i=1

10. Aug 23, 2014

### johann1301

forget m :)

11. Aug 23, 2014

### Mogarrr

I think you meant to write...

$\sum_{n=1}^{m} \frac 1{\sqrt{n}} > \frac 2{\sqrt{m+1}} -1$.

If this is the case, here's a way to start the inductive step:

$\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = ( \sum_{n=1}^{m} \frac 1{\sqrt{n}}) + \frac 1{\sqrt{m+1}}$

12. Aug 23, 2014

### johann1301

no, it is 2(√(n+1) -1) = 2√(n+1) -2

13. Aug 23, 2014

### Mogarrr

Let me know if you'd like more hints, but I'm pretty sure you can finish the problem from here ;)

Last edited by a moderator: Aug 24, 2014
14. Aug 23, 2014

### Mogarrr

Oh... the right hand side is a product. Oops.

That's ok. The steps in the proof won't change much.

15. Aug 23, 2014

### johann1301

$\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = ( \sum_{n=1}^{m} \frac 1{\sqrt{n}}) + \frac 1{\sqrt{m+1}}$

16. Aug 23, 2014

### Mogarrr

Starting from the Left-hand side of the inequality you wish to prove (P(m+1)),

$\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = \sum_{n=1}^{m} \frac 1{\sqrt{n}} + \frac 1{\sqrt{m+1}}$.

Recall that you assumed P(m) to be true, that is

$\sum_{n=1}^{m} \frac 1{\sqrt{n}} > 2 \cdot ((\sqrt{m+1}) -1)$,

So recognizing this, you have...

$\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = \sum_{n=1}^{m} \frac 1{\sqrt{n}} + \frac 1{\sqrt{m+1}} > 2 \cdot ((\sqrt{m+1}) -1) + \frac 1{\sqrt{m+1}}$.

17. Aug 23, 2014

### johann1301

If i contract the right side i get: (2m +3 -2√(m+1))/√(m+1)

Don't see how this is gonna help.. :)

18. Aug 23, 2014

### johann1301

dont i have to show that (2m +3 -2√(m+1))/√(m+1) can be written as 2(√(m+2) -1) to prove it...?

or maybe not since its an inequality...?

Last edited: Aug 23, 2014
19. Aug 23, 2014

### Mogarrr

If you plug in some numbers you'll see...

$2 \cdot (\sqrt{m+1} - 1) + \frac 1{\sqrt{m+1}} \neq 2 \cdot (\sqrt {(m+1)+1} - 1)$.

You're next step should be to show that...

$2 \cdot (\sqrt{m+1} - 1) + \frac 1{\sqrt{m+1}} > 2 \cdot (\sqrt {(m+1)+1} - 1)$.

20. Aug 23, 2014