Proving Ʃ 1/√k ≥ 1/√n with Induction

[srfriggen]

Homework Statement

Ʃ 1/√k ≥ 1/√n (under sigma should be "k=1" and above should be "n", and n is a positive integer)

Homework Equations

The Attempt at a Solution

I. Base case when n=1 is correct.

II. Inductive Hypothesis: Assume true for k=m, where k<m<n, m is a positive integer.

III. Ʃ 1/√m + 1/√m+1 ≥ 1/√n, since Ʃ 1/√m ≥ 1/√n, and Ʃ 1/√m + 1/√m+1 ≥ Ʃ 1/√m.

By the principle of induction, Ʃ 1/√k ≥ 1/√n.

(I'm sorry for leaving out some subscripts under epsilon. I couldn't find how to get k=1 under there or "n" above).

 

[brmath]

You are on the right track, but I find your presentation a little unclear.

You should start by saying the result it true for n = 1.

Then you assume ##\sum_{k = 1}^n (1/\sqrt{k}) \ge 1/\sqrt{n}##. Given this assumption you must show that ##\sum_{k = 1}^{n+1} (1/\sqrt{k}) \ge 1/\sqrt{n+1}##. This is not what you wrote in your step 3.

 

[srfriggen]

You are on the right track, but I find your presentation a little unclear.

You should start by saying the result it true for n = 1.

Then you assume ##\sum_{k = 1}^n (1/\sqrt{k}) \ge 1/\sqrt{n}##. Given this assumption you must show that ##\sum_{k = 1}^{n+1} (1/\sqrt{k}) \ge 1/\sqrt{n+1}##. This is not what you wrote in your step 3.

I thought I had to make the assumption for an arbitrary k (or "n", I'm a bit confused on this one). Otherwise we are assuming the statement we are trying to prove is true.

 

[Mark44]

Let's look at three statements:
P(1): ## 1/\sqrt{1} \geq 1/\sqrt{1}##
P(k): ##\sum_{k = 1}^n (1/\sqrt{k}) \geq 1/\sqrt{n}##
P(k + 1): ##\sum_{k = 1}^{n + 1} (1/\sqrt{k}) \geq 1/\sqrt{n + 1}##

You assume that the 2nd of these is true. You then show (prove) that the 3rd of these is true, using the 2nd.

That's how it works.

 

[srfriggen]

P(k+1):[itex]\sum[/itex][itex]^{n+1}_{k=1}[/itex](1/√k)=[itex]\sum[/itex][itex]^{n}_{k=1}[/itex](1/√k)+(1/[itex]\sqrt{n+1}[/itex]).

[itex]\sum[/itex][itex]^{n}_{k=1}[/itex](1/√k)≥1, and so [itex]\sum[/itex][itex]^{n}_{k=1}[/itex](1/√k)+(1/[itex]\sqrt{n+1}[/itex])≥[itex]\sqrt{n}[/itex].

 

[brmath]

I thought I had to make the assumption for an arbitrary k (or "n", I'm a bit confused on this one). Otherwise we are assuming the statement we are trying to prove is true.

I know it looks like you are assuming what you are trying to prove, but you aren't actually. You are proving that if it works for n it works for n+1. Nobody said it does in fact work for n. Not yet.

What you are doing is bootstrapping. First you establish it is good for n = 1. Then you say, well if it is good for n = 1, can I show it is good for n = 2? If it is good for n = 2, can I show it is good for n = 3? And in general can I show that if it good for n = m then can I show it is good for n = m+1?

Once you have established the general case, then you've shown it is true for any value of n.

However, except for explaining, we don't use the term "m". We just say if it is good for n can I show it is good for n + 1? Same difference.

Occasionally, starting at n = 1 is not the right thing. In special cases you might have to start at a higher number. Those will be pretty obvious, because there won't be any 1 around to start from.

 

[srfriggen]

I know it looks like you are assuming what you are trying to prove, but you aren't actually. You are proving that if it works for n it works for n+1. Nobody said it does in fact work for n. Not yet.

What you are doing is bootstrapping. First you establish it is good for n = 1. Then you say, well if it is good for n = 1, can I show it is good for n = 2? If it is good for n = 2, can I show it is good for n = 3? And in general can I show that if it good for n = m then can I show it is good for n = m+1?

Once you have established the general case, then you've shown it is true for any value of n.

However, except for explaining, we don't use the term "m". We just say if it is good for n can I show it is good for n + 1? Same difference.

Occasionally, starting at n = 1 is not the right thing. In special cases you might have to start at a higher number. Those will be pretty obvious, because there won't be any 1 around to start from.

Thank you for that, that is the best explanation of induction I have ever heard! I've read about it tons of times, watched videos, lectures, but something in what you said finally made it "click". I understand now that the inductive hypothesis doesn't have anything to due with the validity of P(n), and deals with the CONDITIONAL, If P(n) then P(n+1). Wow, thank you!

It seems clear to me now that we can simply continue the 3 steps of the induction process without changing variables, but in every book I have they specify this:

1. P(1) is True
2. For every Natural number, k, If P(k) is true, then P(k+1) is true.
3. Then P(n) is true for all natural numbers, n.

Is it just convention to change from n to k, or is the book just being a little nit-picky?

Also, did you read my final result? Was that correct?

 

[brmath]

The book is trying hard to explain things, and it either is or is not clearer to bounce around between k's and n's. In general, prove it's true for 1, then prove that if it is true for n it is true for n+1.

Your last line is not correct. ##\sum_{k=1}^n## is not greater than 1; all you know is that it is ##\ge 1/\sqrt n ##. Also, what you are trying to prove is that the sum is > ##1/\sqrt{n+1}##.

Were you told to do this by induction? It works, but it is not the easiest way.

 

[srfriggen]

I was not told to use induction, however, this was a test question and we had just finished the induction section. I saw positive integers and assumed it would be the way to prove it.

What other proof method would you suggest I take a look at? Perhaps there is a similar example you can point me to so I can figure it out on my own?

 

[srfriggen]

I would say the last line should be: 1/√k ≥ √n ≥ 1/√(n+1)

 

[brmath]

I would not say that is the last line. Perhaps you should take a break and look at it again tomorrow.

Re an easier way to prove it, the fact is that ##\sum_{k=1}^n 1/\sqrt k = \sum_{k=1}^{n-1} 1/\sqrt k + 1/\sqrt n \ge 1/\sqrt n## because all the previous terms are positive.

I suspect the problem really was ##\sum_{k=1}^n 1/\sqrt k \ge \sqrt n## which at least is not trivially true, and would be a good induction example. Why don't you check your problem again.

 

[Ray Vickson]

I would not say that is the last line. Perhaps you should take a break and look at it again tomorrow.

Re an easier way to prove it, the fact is that ##\sum_{k=1}^n 1/\sqrt k = \sum_{k=1}^{n-1} 1/\sqrt k + 1/\sqrt n \ge 1/\sqrt n## because all the previous terms are positive.

I suspect the problem really was ##\sum_{k=1}^n 1/\sqrt k \ge \sqrt n## which at least is not trivially true, and would be a good induction example. Why don't you check your problem again.

I agree that the problem as stated by the OP is trivial and not worthy of illustrating induction. Your modified version seems to be true (at least numerically for n ≤ 150) and is certainly a more interesting and more worthwhile statement to try to prove.

 

[srfriggen]

I would not say that is the last line. Perhaps you should take a break and look at it again tomorrow.

Re an easier way to prove it, the fact is that ##\sum_{k=1}^n 1/\sqrt k = \sum_{k=1}^{n-1} 1/\sqrt k + 1/\sqrt n \ge 1/\sqrt n## because all the previous terms are positive.

I suspect the problem really was ##\sum_{k=1}^n 1/\sqrt k \ge \sqrt n## which at least is not trivially true, and would be a good induction example. Why don't you check your problem again.

I'm sorry, I did in fact copy the problem incorrectly. Your version is right, and I figured it out. Without going through all the formalities, here is the end of my proof:

1. [itex]\sum[/itex][itex]^{n+1}_{k=1}[/itex](1/[itex]\sqrt{k}[/itex])≥[itex]\sqrt{n+1}[/itex]

2. [itex]\sum^{n}_{k=1}[/itex](1/[itex]\sqrt{k}[/itex])+(1/[itex]\sqrt{n}[/itex])≥[itex]\sqrt{n+1}[/itex]

3. Since [itex]\sum^{n}_{k=1}[/itex](1/[itex]\sqrt{k}[/itex])≥[itex]\sqrt{n}[/itex] we can write:

4. [itex]\sqrt{n}[/itex]+(1/[itex]\sqrt{n}[/itex])≥[itex]\sqrt{n+1}[/itex]

5. Squaring both sides and moving terms around yields:

1+1/n≥0.


I am pretty sure this is correct. Perhaps my reasoning for step 3 could be a little clearer. I'm not sure how else to word it.

 

[brmath]

This one is correct. The presentation could be improved this way:

For step one state that this is what is to be proved based on the hypothesis. At each subsequent step you need to say that they are equivalent -- i.e. the implication goes both ways. That is because when you get to the bottom you have something you know to be true, but now you have to start there and deduce what you were trying to prove. In other words the implications have to run in reverse.

Not sure? Aren't there plenty of examples where a ##\Rightarrow## b does not imply b ##\Rightarrow## a?

Another detail you might attend to if you are trying to be quite perfect is the ##\sqrt k## has two values, + and -. So you could indicate you are only considering positive square roots.

 

[Mark44]

Another detail you might attend to if you are trying to be quite perfect is the ##\sqrt k## has two values, + and -.

Nope - the expression ##\sqrt{k}## has one value, which is greater than or equal to zero. It's true that every positive number has two square roots, but the symbol ##\sqrt{k}## represents the positive one.

I am assuming that k is a nonnegative real number, which is a perfectly valid assumption in the context of this problem.

 

[brmath]

Yes, it was the right assumption for this problem. I'm not sure what ##\sqrt k## represents generally. I think in some contexts both roots would be under consideration; indeed that could be the point of some problems. And it would be nice if in those cases they said to consider negative numbers, but they don't always. You pick it up from context.

 

[Mark44]

My main point was that ##\sqrt{k}## represents the positive square root of k. It does NOT represent two values. If it did we could write the quadratic formula like this:
$$x = \frac{-b + \sqrt{b^2 - 4ac}}{2a}$$
I.e., without the ±.