Prove 2^n > n by induction (1 Viewer)

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

1. The problem statement, all variables and given/known data

prove 2^n > n by induction

2. Relevant equations



3. 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
 
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.
 
31,919
3,891
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

Science Advisor
Homework Helper
Insights Author
Gold Member
3,384
179
"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

[tex]2^k > k[/tex]

Try multiplying both sides by something appropriate.
 

jbunniii

Science Advisor
Homework Helper
Insights Author
Gold Member
3,384
179
By the way, an interesting non-inductive way to prove the same thing is to expand

[tex]2^n = (1 + 1)^n[/tex]

using the binomial theorem.
 

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top