Jump to content

Proving an Inequality by Induction


Science Student
 Share

Recommended Posts

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?

 

 

 

Link to comment
Share on other sites

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 by John
Link to comment
Share on other sites

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 by Science Student
Link to comment
Share on other sites

 

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 by John
Link to comment
Share on other sites

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 by Science Student
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.