Proving an Inequality by Induction

[Science Student]

Here's my attempt at the answer to the following question:

 

Question: Use induction to prove that 3^n > n x 2^n for every natural number n ≥ 3

 

Answer:

 

Step 1: 3^3 > 3 x 2^3 ⇒ 27 > 24

 

Step 2: Assume 3^k > k x 2^k

 

Step 3: 3^(k+1) > (k+1) x 2^(k+1) ⇒ 3 x 3^k > k x 2^(k+1) + 2^(k+1) ⇒

3^k + 3^k + 3^k > k x 2^k + k x 2^k + 2^k + 2^k.

 

So am I allowed to use the assumption as a given to make the green and red parts of the inequality true?

 

And am allowed to just plug in the base k value that would show the black parts of the inequality to be true?

 

Another thing that I don't understand about induction is why we have to assume that the inequality in the question is true for k. If k can only be the base case in the beginning, then why do we have to assume that it works for some k when we just showed that it works when k is the base case?

 

 

 

[John]

Your step 3 reads like you're assuming what you're trying to prove. You've assumed 3^k > k * 2^k for some k, and you must show how this implies that the inequality holds for k + 1. But your step 3 starts out stating the latter as fact.

You're allowed to use the assumption as part of your proof, yes.

 

No, you can't just plug in the base value. The base value and k aren't the same thing.

 

The way induction works is as follows:

 

1. We show the statement holds for some base value.

2. Under the assumption that the statement holds for some value k (which is not necessarily the base value), we show that it holds for k + 1.

3. Therefore, the statement holds for all k greater than or equal to the base value.

 

In your problem here, you first demonstrate that the inequality holds for 3. From that, you are to show that if it holds for any k >= 3, then it must hold for k + 1. Thus you will have shown that since the inequality holds for 3, it must also hold for 4, and thus also for 5, and for 6, etc.

Edited November 11, 2013 by John

[Science Student]

Your step 3 reads like you're assuming what you're trying to prove. You've assumed 3^k > k * 2^k for some k, and you must show how this implies that the inequality holds for k + 1. But your step 3 starts out stating the latter as fact.

 

You're allowed to use the assumption as part of your proof, yes.

 

No, you can't just plug in the base value. The base value and k aren't the same thing.

 

The way induction works is as follows:

 

1. We show the statement holds for some base value.

2. Under the assumption that the statement holds for some value k (which is not necessarily the base value), we show that it holds for k + 1.

3. Therefore, the statement holds for all k greater than or equal to the base value.

 

In your problem here, you first demonstrate that the inequality holds for 3. From that, you are to show that if it holds for any k >= 3, then it must hold for k + 1. Thus you will have shown that since the inequality holds for 3, it must also hold for 4, and thus also for 5, and for 6, etc.

 

 

Ohhhh, so I did step 3 backwards? Don't worry about responding if the answer is yes. And - thank-you - in advance.

Edited November 11, 2013 by Science Student

[imatfaal]

You have to reduce and simplify your inequality till it is incontrovertible - if you still have n's or k's floating about you have to be careful, see if you cannot get rid of them

[John]

 

Ohhhh, so I did step 3 backwards? Don't worry about responding if the answer is yes. And - thank-you - in advance.

 

Well, I see you said not to worry about responding, but I thought I should clarify.

 

There's nothing wrong with starting with the desired conclusion and working backwards, so long as you make sure your steps are reversible. In your final written proof, you'll need to remember to do this reversal, so that the inductive step proceeds from the assumption to the conclusion, rather than from the conclusion to the assumption.

Edited November 11, 2013 by John

[Science Student]

You have to reduce and simplify your inequality till it is incontrovertible - if you still have n's or k's floating about you have to be careful, see if you cannot get rid of them

Thankfully, our professor made us do this in the beginning of the year so that we don't have to do it anymore. a < b, a + a < b + a, a + b < b + b, therefore a + a < b + b etc.

 

I think that I know what you mean now. Never mind what I put above.

 

Well, I see you said not to worry about responding, but I thought I should clarify.

 

There's nothing wrong with starting with the desired conclusion and working backwards, so long as you make sure your steps are reversible. In your final written proof, you'll need to remember to do this reversal, so that the inductive step proceeds from the assumption to the conclusion, rather than from the conclusion to the assumption.

Oh, I see. My professor seems to give us answers mine, but he explains it in further detail in words after, which is what I didn't do. Thanks again.

Edited November 11, 2013 by Science Student