Mathematical Induction Proof

1. Apr 19, 2010

amiv4

1. The problem statement, all variables and given/known data
Prove that for all the natural numbers n that 2^n > n

2. Relevant equations

3. The attempt at a solution
Base Case is easy
Then the inductive step you have 2^k > k as the inductive hypothesis
show that p[k+1] holds
2^(k+1) > k+1
on the left side 2^(k+1) = 2^k * 2
but idk what else to do

2. Apr 19, 2010

LCKurtz

And what does your induction hypotheses tell you about the 2k on the right side of that last equation? And after you answer that, what are you wanting thge right side of the inequality to be greater than?

3. Apr 19, 2010

amiv4

Well 2^k * 2 > 2^k > k. And im guessing you are talking about k+1 and idk what i want that to be greater than. It is greater than k but idk how that helps

4. Apr 19, 2010

LCKurtz

But you are giving away something by dropping the 2. You have:

2k+1 = 2k*2 so far, and you know 2k > k

Use that without dropping anything else and see if you can see the result is > k + 1.