Proving Induction: n∑(1/√n) > 2(√(n+1) -1)

[johann1301]

Homework Statement

Prove this by induction

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

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...

 

[Ray Vickson]

Homework Statement

Prove this by induction

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

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...

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

 

[johann1301]

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

 

[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}} ?

 

[johann1301]

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}} ?

woops!, i can correct it...

 

[johann1301]

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

 

[johann1301]

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

 

[Mogarrr]

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

Um, what is m?

 

[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

 

[johann1301]

Um, what is m?

forget m :)

 

[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}}

 

[johann1301]

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

 

[Mogarrr]

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

 

[Mogarrr]

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

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

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

 

[johann1301]

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

I already knew this, but how am i supposed to compare this result to the right side? the expression on the right side is impossible to write as a sum of any sort...? At least : 2√(m+2)...

 

[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}}.

 

[johann1301]

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

Don't see how this is going to help.. :)

 

[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...?

 

[Mogarrr]

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...?

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).

 

[Ray Vickson]

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

I already knew this, but how am i supposed to compare this result to the right side? the expression on the right side is impossible to write as a sum of any sort...? At least : 2√(m+2)...

Your problem is to show that
2 \sqrt{n+1}-2 + \frac{1}{\sqrt{n+1}} \geq 2 \sqrt{n+2} - 2,\\<br /> \text{or}\\<br /> \sqrt{n+2} - \sqrt{n+1} \leq \frac{1}{2 \sqrt{n+1}}
If I were doing it I would write
\sqrt{n+2} = \sqrt{n+1} \left( 1 + \frac{1}{n+1} \right)^{1/2}
and go on from there.

 

[johann1301]

yes, i got 9/4 > 8/4! or 9>8 thanks!, now its just about proving the basecase and its finished?

 

[Ray Vickson]

yes, i got 9/4 > 8/4! or 9>8 thanks!, now its just about proving the basecase and its finished?

Which message are you responding to? Please use the "Quote" button, so that the discussion can be followed accurately.

 

[johann1301]

Which message are you responding to? Please use the "Quote" button, so that the discussion can be followed accurately.

both of them :) the inequality that both of you posted implies that 9>8. Since this is true, the inequality you posted must be true ?

 

[Ray Vickson]

both of them :) the inequality that both of you posted implies that 9>8. Since this is true, the inequality you posted must be true ?

I have no idea what you are talking about; we need to know something for all n (or at least, for all n larger than, say, 2 or 3), so 8 and 9 have nothing to do with the problem.

 

[Mogarrr]

both of them :) the inequality that both of you posted implies that 9>8. Since this is true, the inequality you posted must be true ?

We've invested a lot of time helping you out, so we would like to see you get the right answer. Could you post how you came to this conclusion?

 

[johann1301]

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

Your problem is to show that
2 \sqrt{n+1}-2 + \frac{1}{\sqrt{n+1}} \geq 2 \sqrt{n+2} - 2,\\<br /> \text{or}\\<br /> \sqrt{n+2} - \sqrt{n+1} \leq \frac{1}{2 \sqrt{n+1}}

This inequality implies that 9>8. And that is certainly true, therefore the inequality that you posted must be true.

 

[johann1301]

2 \sqrt{n+1}-2 + \frac{1}{\sqrt{n+1}} \geq 2 \sqrt{n+2} - 2,\\<br /> \text{or}\\<br /> \sqrt{n+2} - \sqrt{n+1} \leq \frac{1}{2 \sqrt{n+1}}

if i multiply by √n+1 on both sides, i get..

√((n+2)(n+1)) - (n+1) < 1/2

√(n²+3n+2) < (1/2) + (n+1)

√(n²+3n+2) < n+(3/2)

n²+3n+2 < (n+(3/2))²

n²+3n+2 < n²+3n+(9/4)

2 < (9/4)

(8/4) < (9/4)

8 < 9

 

[johann1301]

We've invested a lot of time helping you out, so we would like to see you get the right answer. Could you post how you came to this conclusion?

You have been a great helper! Both of you have :) I believe I've learned some new tricks because of this :)

 

[HallsofIvy]

This inequality implies that 9>8. And that is certainly true, therefore the inequality that you posted must be true.

No, this is incorrect "logic". The fact that "A implies B" and "B is true" does NOT mean "A is true".

 

[johann1301]

No, this is incorrect "logic". The fact that "A implies B" and "B is true" does NOT mean "A is true".

So how do you show that the inequality is true?

 

[vela]

You know that
$$\sum_{k=1}^{n+1} \frac{1}{\sqrt k} > 2(\sqrt{n+1}-1) + \frac {1}{\sqrt{n+1}}.$$ Starting from there, you have to find a chain of true implications that eventually ends with
$$\sum_{k=1}^{n+1} \frac{1}{\sqrt k} > 2(\sqrt{n+2}-1).$$ A few posts back you said that you found
$$2(\sqrt{n+1}-1) + \frac {1}{\sqrt{n+1}} = \frac{2n+3-2\sqrt{n+1}}{\sqrt{n+1}}.$$ First, do a little algebra and show that this means
$$\sum_{k=1}^{n+1} \frac{1}{\sqrt k} > 2\left[\frac{n+\frac 32}{\sqrt{n+1}} - 1\right].$$ If you can now show that
$$2\left[\frac{n+\frac 32}{\sqrt{n+1}} - 1\right] > 2(\sqrt{n+2}-1),$$ you can use the transitive property of > to get the result you want. It's clear that this inequality holds if you can show that
$$\frac{n+\frac 32}{\sqrt{n+1}} > \sqrt{n+2}.$$ To prove this last inequality holds, you have to start with a statement that's undeniably true and go from there. What you can't do is start by assuming the inequality is true because that's what you're trying to prove.

What I suggest is that you start with
$$\sqrt{n+2} = \sqrt{n+2}\frac{\sqrt{n+1}}{\sqrt{n+1}}.$$ The goal is to use the rules of algebra to continue to manipulate the righthand side that so that's it's readily apparent that it's less than $\frac{n+\frac 32}{\sqrt{n+1}}$.

You've already done most of the work. It's just putting everything in the right order to make a valid logical argument.

 

[Ray Vickson]

So how do you show that the inequality is true?

The argument you gave above can be made to work: start with the fact that 8 < 9 and work backwards (going through your steps in the opposite order).

Alternatively, use the fact that $\sqrt{1+x} \leq 1 + x/2$ for $|x| < 1$, with strict inequality if $x \neq 0$. You can see this in two ways:
Method (1) look at the graph of $y = \sqrt{z}$; it lies below its tangent line through the point (1,1). The tangent line has slope 1/2, so we have $\sqrt{z} \leq 1 + (1/2)(z-1)$, with equality at $z = 1$ and a strict inequality otherwise.
Method (2): $1 +x \leq 1 + x + x^2/4 = (1 +\: x/2)^2$, so $\sqrt{1+x} \leq 1 + (x/2).$

Anyway, we have
\sqrt{n+2} = \sqrt{n+1}\sqrt{\left(1+\frac{1}{n+1} \right)}\\<br /> \leq \sqrt{n+1} \left( 1 + \frac{1}{2} \frac{1}{n+1} \right) = \sqrt{n+1}<br /> + \frac{1}{2\sqrt{n+1}}

 

[johann1301]

I have to get back to this problem at a later point, have some other things i have to go through before next lectures! But thank you all so much for your help!