ngluth said:
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.
