Proof by induction

  • Thread starter johann1301
  • Start date
  • #26
217
1
[itex]\sum_{n=1}^{m+1} \frac 1{\sqrt{n}} = ( \sum_{n=1}^{m} \frac 1{\sqrt{n}}) + \frac 1{\sqrt{m+1}} [/itex]

Your problem is to show that
[tex] 2 \sqrt{n+1}-2 + \frac{1}{\sqrt{n+1}} \geq 2 \sqrt{n+2} - 2,\\
\text{or}\\
\sqrt{n+2} - \sqrt{n+1} \leq \frac{1}{2 \sqrt{n+1}}[/tex]

This inequality implies that 9>8. And that is certainly true, therefore the inequality that you posted must be true.
 
  • #27
217
1
[tex] 2 \sqrt{n+1}-2 + \frac{1}{\sqrt{n+1}} \geq 2 \sqrt{n+2} - 2,\\
\text{or}\\
\sqrt{n+2} - \sqrt{n+1} \leq \frac{1}{2 \sqrt{n+1}}[/tex]

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

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

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

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

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

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

2 < (9/4)

(8/4) < (9/4)

8 < 9
 
  • #28
217
1
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 :)
 
  • #29
HallsofIvy
Science Advisor
Homework Helper
41,847
965
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".
 
  • #31
vela
Staff Emeritus
Science Advisor
Homework Helper
Education Advisor
15,093
1,674
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.
 
  • #32
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722
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
[tex] \sqrt{n+2} = \sqrt{n+1}\sqrt{\left(1+\frac{1}{n+1} \right)}\\
\leq \sqrt{n+1} \left( 1 + \frac{1}{2} \frac{1}{n+1} \right) = \sqrt{n+1}
+ \frac{1}{2\sqrt{n+1}}[/tex]
 
  • #33
217
1
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!
 

Related Threads on Proof by induction

  • Last Post
Replies
6
Views
871
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
661
  • Last Post
Replies
3
Views
928
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
769
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
9
Views
1K
Top