How can 2^n > n be proven by induction?

[Archetype2]

Homework Statement

prove 2^n > n by induction

Homework Equations

The Attempt at a Solution

In my math class we start off assuming 2^n > n is true for n=k.
Then we try to prove that when n=k+1 the inequality is true. So,I
start off going, 2^(k+1) > (k+1) which is equivalent to 2*2^k > (k+1)

which is then equivalent to 2^k+2^k > (k+1) then my math teacher said

to make the next step which is, since we assumed that 2^k > k then 2^k

+ 2^k > k+k and then he said that k+k > (k+1) and that was the end of

the proof. I do not get this last part at all, since I thought that
when you prove something by induction, it's going to be proven for all
numbers but we only proved that the inequality is true for k>1

 

[lkh1986]

There are all together 3 steps to the mathematical induction. You have left out the first step, namely showing the inequality holds true for the case when n = 1. Now, when n = 1, 2^1 = 2 > 1.

So he case is true when n = 1.

Then you proceed to the case where n = k, and finally n = k+1.

So when your k = 1 is true, (because you have shown that the inequality holds when n = k = 1), your k + 1 = 2 is also true.

When k = 2 is true, k + 1 = 3 is also true. And the rest is just like the dominoes effect.

I might be wrong, but that's my understanding regarding mathematical induction.

 

[Mark44]

There are all together 3 steps to the mathematical induction. You have left out the first step, namely showing the inequality holds true for the case when n = 1. Now, when n = 1, 2^1 = 2 > 1.

This is usually called the base case. It doesn't have to be for n = 1, but often is.

So he case is true when n = 1.

Then you proceed to the case where n = k, and finally n = k+1.

The idea is that you assume that your statement is true for n = k (the induction hypothesis), and then use that to show that the statement is also true for n = k + 1.

So when your k = 1 is true, (because you have shown that the inequality holds when n = k = 1), your k + 1 = 2 is also true.

When k = 2 is true, k + 1 = 3 is also true. And the rest is just like the dominoes effect.

I might be wrong, but that's my understanding regarding mathematical induction.

 

[Archetype2]

"The idea is that you assume that your statement is true for n = k (the induction hypothesis), and then use that to show that the statement is also true for n = k + 1."

Yes, I understand that this is the objective, but I am wondering if there is a general method of doing this and how you would you do it for 2^(k+1) > (k+1)

 

[jbunniii]

"The idea is that you assume that your statement is true for n = k (the induction hypothesis), and then use that to show that the statement is also true for n = k + 1."

Yes, I understand that this is the objective, but I am wondering if there is a general method of doing this and how you would you do it for 2^(k+1) > (k+1)

Well, if it's true for n = k then

$$2^k > k$$

Try multiplying both sides by something appropriate.

 

[jbunniii]

By the way, an interesting non-inductive way to prove the same thing is to expand

$$2^n = (1 + 1)^n$$

using the binomial theorem.