# Prove 2^n > n by induction

## Homework Statement

prove 2^n > n by induction

## 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

Related Precalculus Mathematics Homework Help News on Phys.org
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
Mentor
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.

"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
Homework Helper
Gold Member
"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
$$2^n = (1 + 1)^n$$