# Proof of $2^n > n$ by Induction

I'm new to induction and trying to prove $$2^n > n$$ for all natural numbers.

I've seen a couple of examples but am confused about the the case going from $$k = 1$$ to $$k =2$$.

So I show $$2^1 > 1$$ as the base case.

Then I assume $$2^k > k$$

Meaning that

$$2.2^k > 2k$$

i.e.

$$2^{k+1} > 2k$$

Or

$$2^{k+1} > k + k > k + 1$$

So it is considered proven.

But when $$k = 1$$, $$k + k \not> k + 1$$

Do I need a special case for going from $$k=1$$ to $$k=2$$?
• Adding a special case when $k=1$ is a perfectly valid solution. Saying $k+k\geq k+1$ for $k\geq1$ is probably nicer though. Dec 12, 2018 at 9:45
Technically, the statement $$2^{k+1} > k+k>k+1$$ is wrong, precisely because $$k$$ could be $$1$$. You can, however, write $$2^{k+1} > k+k \geq k+1$$
and from that, you can still conclude that $$2^{k+1}>k+1$$. No special case needed, since $$a>b$$ and $$b\geq c$$ always implies $$a>c$$.
No, you don't need a special case. $$2^{k+1} >2k$$ and $$2k \geq k+1$$ together impliy $$2^{k+1} >k+1$$