# Prove by Induction : $n < 2^n$ [duplicate]

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.

## marked as duplicate by GNUSupporter 8964民主女神 地下教會, B. Mehta, samerivertwice, José Carlos Santos, ahulpkeMay 10 '18 at 20:59

• $2^{n+1} \leq 2^n.2$ instead of $2^{n+1}< 2^n$ should be better. – Seirios Oct 11 '14 at 21:45

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.$$

• I never understood why people need to use unnecessary variables for induction. Why $k$? Why not just "assume it holds for $n$? If you're going to say $k$ you have to go through the hassle of saying "Let $k \in \mathbb{N}$ ... – Zubin Mukerjee Oct 11 '14 at 21:52
• I am not sure how did you get the $2^k + 2^k$... some more explanations will be appreciated! – FarahFai Oct 11 '14 at 21:55
• @FarahFai: You understand $k+1\lt 2^k+1$ and $1\lt 2^{k}$, right? Then, we have $1\color{red}{+2^k}\lt 2^k\color{red}{+2^k}$. – mathlove Oct 11 '14 at 22:00
• @ZubinMukerjee: Because I was taught to do so:) – mathlove Oct 11 '14 at 22:13
• @ZubinMukerjee I think the pedagogical value is that there is less confusion with the variables. But personally I think there is more pedagogical value in learning how to deal with dummy variables. So I agree with you. – Git Gud Oct 11 '14 at 23:18

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}.$$

• can you please explain a little bit more on how did you get the $2^n + 2^n$? – FarahFai Oct 11 '14 at 21:58
• Sure. Since $n\ge 1$, $2^n$ is at least $2^1 = 2$, so $1<2^n$. Now add $2^n$ to both sides of that inequality. – rogerl Oct 11 '14 at 21:59

The inductive step

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