Can't prove $2^n > n$ with Mathematical Induction

Question

As the title states, I have a problem with proving $2^n > n$

I can do the basis step fine: Basis step:

"n = 1"

2^1 = 2
2 > 1

So it is true for $n$.

But then I get stuck with the inductive step. Here's how I tried, but then I get stuck. I don't know what to do.

Inductive step:
"Assume true for n"
"Prove for n+1"

  2^(n+1) > n+1

= 2^1 * 2^n
= 2*2^n
= 1*2^n + 2^n
= 2^n + 2^n > n+1

If you know the answer, please explain it to me so I know how to do it in the future. Any help is appreciated.

Answer 1

For $n=1$, we have $2^1=2>n=1$. Now, assume that for some $k>1$ we have

$$2^k>k \tag 1$$

Then, we have

$$\begin{align} 2^{k+1}&=2(2^k) \tag 2\\\\ &>2(k) \tag 3\\\\ &=k+k \tag 4\\\\ &>k+1 \tag 5 \end{align}$$

for $k>1$.

Notes:

In going from $(2)$ to $(3)$, we used the assumption $2^k>k$ as given in $(1)$.

Then, in arriving at $(4)$, we simply used the fact that $2k=k+k$.

Finally, since $k>1$, $k+k>k+1$.

Therefore, by the principal of mathematical induction, $2^n>n$ for $n\ge 1$.

Answer 2

If $n = 1$, then $2^{n} = 2 > n = 1$; if $n \geq 1$ is such that $2^{n} > n$, then $2^{n+1} = 2\cdot 2^{n} > 2n \geq n+1$; hence by mathematical induction we are done.