• Support PF! Buy your school textbooks, materials and every day products Here!

Prove 2^n > n by induction

  • Thread starter Archetype2
  • Start date
  • #1

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
 

Answers and Replies

  • #2
99
0
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.
 
  • #3
33,508
5,193
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.
 
  • #4
"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)
 
  • #5
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
"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.
 
  • #6
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
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.
 

Related Threads on Prove 2^n > n by induction

  • Last Post
Replies
14
Views
16K
  • Last Post
Replies
7
Views
1K
Replies
5
Views
921
Replies
15
Views
76K
Replies
12
Views
2K
Replies
8
Views
1K
  • Last Post
Replies
3
Views
2K
Replies
4
Views
5K
Replies
5
Views
3K
Top