Proving 2n > n by Induction: A Simple Homework Solution

[missavvy]

Homework Statement

Prove by induction on n that n belonging to N (set of natural #'s)
2ⁿ > n

Homework Equations

The Attempt at a Solution

So here's my stab at it!

Base case: n = 0 (My prof includes 0 in N)

2⁰ > 0, 1 >0
True. So this works for the base case.

Assume this holds for n. Let n = k+1

2^(k+1) > k + 1

Here is where I'm a bit confused..
I'm not sure if it should be:

2(2^k) > k + 1
> 2k

OR

2^k + 1 > k + 1

And with either one, how do I continue??

Eekkk. any help is appreciated! Thanks.

 

[Dick]

You tell me. Is 2^(k+1) equal to (2^k)+1 or is it 2*(2^k)? You must know something about how exponents work, right?

 

[jgens]

Base case: n = 0 (My prof includes 0 in N)

2⁰ > 0, 1 >0
True. So this works for the base case.

This is perhaps a bit nitpicky, but you should probably write 2⁰ = 1 > 0.

Assume this holds for n. Let n = k+1

This should be something along the lines of: "Assume this relation holds for the natural number k. If we can show that this implies that the relation holds for the natural number k+1, then we know that it holds for all natural numbers."

Granted, my statement is quite verbose, but it makes it clear in what direction the proof is headed and doesn't leave near as much room for confusion.

2^(k+1) > k + 1

Here is where I'm a bit confused..
I'm not sure if it should be:

2(2^k) > k + 1
> 2k

OR

2^k + 1 > k + 1

And with either one, how do I continue??

Eekkk. any help is appreciated! Thanks.

I think that you've managed to confuse yourself here. By the statement above, you already know that 2^k > k. All you now need to show is that 2^k+1 > k+1 must be true. To do this, note that 2^k+1 = 2*2^k > 2k. Now, can you prove that 2k > k+1?