Proving an Inequality by Induction

[student34]

Homework Statement

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

Homework Equations

N/A

The Attempt at a Solution

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?

 

[Hyrum]

I'm going to start by explaining what exactly induction is. Induction is the process of proving a condition to be true for every element in a given set by showing that if it's true for one, it's true for all. To answer your question "So am I allowed to use the assumption as a given to make the green and red parts of the inequality true?" Absolutely, this is the idea behind induction. In your example, you're attempting show that if it's true for k, it must be true for k+1. Therefore, you assume it must be true for k and then show it to be true for k+1. After this, you test it on k = 3, Since it holds true for k = 3, you know it must for k = 4 and so on.

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

You mean k = 3? No. As I said above, you must show it to be true for all k + 1 where it is true for k.

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?

As I said above, you must do this to show it is true for all natural number.


In short, you have a condition C that you want to test on all in S = {3, 4, 5, 6...}

So you first show that C(k) is true implies C(k+1) is true for k in S

Second show C(3) is true making C(4) true making C(5) true making C(6) true etc (Because we've already established the above relation).


Hope it helps. It's probably pretty confusing.

 

[LCKurtz]

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?

I will try to answer this with a non-mathematical analogy. Suppose you have a child who is just learning to walk. Your building has a fire escape ladder on the side of the building that goes to the roof and whose first rung is 3 feet off the ground. You don't want your child climbing that ladder. What two things must your child master to climb the ladder?

1. He has to solve the problem of getting on the first rung, perhaps by climbing up on a chair or box.

2. He has to know how to get from one rung to the next.

That's the idea behind induction. The case $n=1$ corresponds to getting on the first rung. Now if the child has mastered the mechanics of climbing from one rung to the next, he can climb the ladder. That corresponds to assuming your proposition is true for $n=k$ and showing it is therefore true for $n=k+1$. You know if the child is on any rung, he can get to the next. You know if your proposition is true for $n=k$ then it is true for $n=k+1$. That's all it takes.

 

[student34]

I'm going to start by explaining what exactly induction is. Induction is the process of proving a condition to be true for every element in a given set by showing that if it's true for one, it's true for all. To answer your question "So am I allowed to use the assumption as a given to make the green and red parts of the inequality true?" Absolutely, this is the idea behind induction. In your example, you're attempting show that if it's true for k, it must be true for k+1. Therefore, you assume it must be true for k and then show it to be true for k+1. After this, you test it on k = 3, Since it holds true for k = 3, you know it must for k = 4 and so on.


As I said above, you must do this to show it is true for all natural number.


In short, you have a condition C that you want to test on all in S = {3, 4, 5, 6...}

So you first show that C(k) is true implies C(k+1) is true for k in S

Second show C(3) is true making C(4) true making C(5) true making C(6) true etc (Because we've already established the above relation).


Hope it helps. It's probably pretty confusing.

Yeah, that totally helps - thanks!

 

[student34]

I will try to answer this with a non-mathematical analogy. Suppose you have a child who is just learning to walk. Your building has a fire escape ladder on the side of the building that goes to the roof and whose first rung is 3 feet off the ground. You don't want your child climbing that ladder. What two things must your child master to climb the ladder?

1. He has to solve the problem of getting on the first rung, perhaps by climbing up on a chair or box.

2. He has to know how to get from one rung to the next.

That's the idea behind induction. The case $n=1$ corresponds to getting on the first rung. Now if the child has mastered the mechanics of climbing from one rung to the next, he can climb the ladder. That corresponds to assuming your proposition is true for $n=k$ and showing it is therefore true for $n=k+1$. You know if the child is on any rung, he can get to the next. You know if your proposition is true for $n=k$ then it is true for $n=k+1$. That's all it takes.

Thank-you, it all clicked, finally :)