Need some help with this induction problem

[ngluth]

Need some help with this induction problem. I have it thus far

P(n) n> or equal ?, 1+2n < 3^n

consider P(1) 1+2(1) < 3^1 = 4<3 no
consider P(2) 1+2(2) < 3^2 = 5<9 yes

since 5<9, P(2) is established

Show that K > or equal 2

if P(k): 1+2k < 3

then P(k+1): 1+2(k+1) < 3^k+1

so 1 + 2k + 2 < 3^k + 3

2k + 3 < 3^k + 3

Question: am I done? Or is there another step I should be looking at?

 

[symbolipoint]

That looks like a fairly good job. Now subtract 3 from both sides; and divide both sides by 2. What do you find? If it is a true statement then I guess you're done.

 

[ngluth]

That is what I figured out. Thanks What a help

 

[ngluth]

Another question:

P(n) 1^2 + 2^2 + 3^2 +…+ n^2 = n(n+1)(2n+1) / 6

Consider: P(1) n^1 = 1(n+1)[(2(1) +1] /6
1^1 = 1(2)(2+1) /6
1 = 6 / 6 or 1
Since 1 = 1 I have established P(1)
P(K) 1^2 + 2^2 + 3^2 +…+ K^2 = K(K+1)(2K+1) /6
Implies P(k+1) 1^2 + 2^2 + 3^2 +…+ K^2 + (k+1)^2 = (k+1)[(k+1)+1][2(k+1)+1] /6
Begin P(k+1) and use P(k)
1^2 + 2^2 + 3^2 +…+ K^2 + (k+1)^2 = k(k+1)(2k+1) /6 + (k+1)^2
Ultimate goal to get k(k+1)(2k+1) /6 + (k+1)^2 to equal k(k+1)(2k+1) /6
Here it goes
Common dem k(k+1)(2k+1) /6 + 6k^2 + 12k + 6 /6 Factor k(2k^2 + 3k +1) + 6k^2 + 12k +6 /6
2k^3 + 3k^2 + k + 6k^2 + 12k + 6 /6
2k^3 + 9k^2 + 13k +6 /6
Factor k(2k^2 + 9k + 13 + 6) /6
K(2k^2 + 9k + 19) /6
Question: Am I in the ball park. It seems very odd to me.

 

[belliott4488]

I think you're on the right track. I like to work backwards from where I'm trying to go sometimes, since that can be easier. In this case, if you expand the right-hand-side (RHS) of the equation that you're tying prove, then you'll know if you've got it right when the LHS looks the same. At that point you can reverse the steps you took on the RHS, apply them to the LHS and get back to where you started with the RHS, which is the point.

Follow that?? ;-)

 

[belliott4488]

That looks like a fairly good job. Now subtract 3 from both sides; and divide both sides by 2. What do you find? If it is a true statement then I guess you're done.

Whoa ... I don't think so! First, that just leaves you with 2 < (3^k)/2 . Are you now going to find all values of k for which this is true?

I think a better approach would use what you've assumed, i.e. that P(k): 1+2k < 3 holds for at least one value of k > 2. You must explicitly use that assumption in your proof; otherwise it's not induction (which is fine if it works, but since this is given as a problem in induction, chances are that's the best way to go).

In this case, you want to show that

P(k+1): 1+2(k+1) < 3 is true IF 1+2k < 3 is true.

Well, is it? What's the difference between the two left sides of these inequalities? If the second one is true, can you see that the first one must be, too? That's what you need prove: if it's true for some k, then it's also true for k+1. That's the basis of induction.

 

[ngluth]

why is the answer not 1+2(k+1) < 3^k+1 I have turned in this assignment so could you Please explain exactly how I would finish this problem. I have not yet completely understood how to prove that if it's true for k, then it's true for k+1.

The problem before the one I got it answered. I did work it backwards and had no problem. Thanks for your help.

 

[belliott4488]

why is the answer not 1+2(k+1) < 3^k+1 I have turned in this assignment so could you Please explain exactly how I would finish this problem. I have not yet completely understood how to prove that if it's true for k, then it's true for k+1.

The problem before the one I got it answered. I did work it backwards and had no problem. Thanks for your help.

Where did you get 1+2(k+1) < 3^k+1? I thought you were left with 2k + 3 < 3^k + 3 ... is that what you meant? In either case, though, how does that prove what you want? You've just found an expression which might or might not be true.

What you have to do for a proof by induction is two things:
1. Show that the expression to be proved is true for one case, i.e. for one specific value of n.
2. Show that if it is true for anyone value of n, then it must also be true for n+1 (this is usually the difficult part).

So, in your case, you have asserted that the expression for P(n) is true for some value of n, i.e. for n=k. Now you have to prove that it is also true for n=k+1. Well, to do that, you need to know what the true value of P(n) is for n=k+1 (how else could you show that the formula will be correct for n=k+1?). So, use the definition of P(n) to say what the expression is for P(k+1):

P(k+1): 1 + 2(k+1) <? 3^(k+1) (where the ? mark indicates that we don't know yet if this is true.)

Well, it is difficult to say whether this is true in general, but that we know it's true for P(k) - so we have to use that (you always have to use that, since that's part of the proof - this part holds if and only if the expression for P(k) is true).

So, P(k): 1 + 2k < 3^k is true - how does this help us? Well, look back at the expression for k+1, and let's rearrange it:

P(k+1): 1 + 2k + 2 <? 3^k * 3 (algebra)
or, (1+2k) + 2 <? (3^k) * 3

Here you notice that the quantities in parentheses are just the quantities in the P(k) inequality (this is what you usually want to do - you obtain something from the n=k case so that you can invoke it to show that the n=k+1 case is also true). What you have is two quantities, and you want to know is if you add 2 to the lesser one and multiply the greater one by three, is the first result still less than the second? This takes some reasoning, watch carefully!

Multiplying a number by 3 means adding adding that number to itself 3 times, so that's like adding two times that number to itself. So, you've added 2 to the left side and 2*something on the right side - will the inequality still be true? Well, if you think about it, it has to be as long as the "something" on the right side is greater than or equal to one, i.e. 2 < 2*x for any x>1. Well, the "something" on the right is 3^k, which is definitely greater than 1.

So ... you start with 1+2^k < 3^k, and if you add 2 to the left side and 2 * 3k to the right side, what you get on the left must be less than what you get on the right. So the new inequality is true.

Okay, so that wasn't very clear or simple ... there might well be an easier way, but that is what first popped out at me. In general, you want to rearrange the k+1 expression in such a way that you can use the k expression to argue that the k+1 expression is also true.

 

[ngluth]

Awesome ! Thank you so much. I did understand the general concept. Your explanation has help clear up a few places that were a little fuzzy. I could complete an induction when the equation was equal but the inequalities are confusing. Thanks again. I appreciate the service you are providing and I am sure I will seek your help again. Thanks. Nancy