Prove by Induction : $n < 2^n$

Question

So I need to prove the inequality :

$$n < 2^n$$ by Induction.

What I have done so far is :

Step $1$: Prove that the statement is true for $n=1$ $$1<2^1$$ (true)

Step $2$: Prove that, if $p(n)$ is true, then $p(n+1)$ is also true.

Assume that $p(n): n < 2^n$ is true. then :

(Add $1$ on both side to get $n+1$) : $$n+1 < 2^n +1$$

(Multiply the original inequality by $2$ to get $2^{n+1}$ ) : $$2^{n+1} < 2^n . 2$$

I don't know where to go from here. In fact, I am not sure whether what I did is true or not. I appreciate any insight and help.

Answer 1

Assume that it holds for $n=k$, i.e. $$k\lt 2^k.$$ Then, we have $$\begin{align}k+1\lt 2^k+1\lt 2^k+2^k=2\cdot 2^k=2^{k+1}.\end{align}$$ Here, note that for $k\ge 1$, we have $$1\lt 2^k.$$

Answer 2

The inductive step

$$2^{n+1}=2\times 2^n>2n\ge n+1$$

Answer 3

You are almost there. You have $n+1 < 2^n+1$, but $1 < 2^n$ for $n\ge 1$, so this gives $$ n+1 < 2^n+1 < 2^n+2^n = 2^{n+1}.$$