This question already has an answer here:

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, ahulpke May 10 '18 at 20:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ $2^{n+1} \leq 2^n.2$ instead of $2^{n+1}< 2^n$ should be better. $\endgroup$ – 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.$$

  • $\begingroup$ 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}$ ... $\endgroup$ – Zubin Mukerjee Oct 11 '14 at 21:52
  • $\begingroup$ I am not sure how did you get the $2^k + 2^k$... some more explanations will be appreciated! $\endgroup$ – FarahFai Oct 11 '14 at 21:55
  • $\begingroup$ @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}$. $\endgroup$ – mathlove Oct 11 '14 at 22:00
  • $\begingroup$ @ZubinMukerjee: Because I was taught to do so:) $\endgroup$ – mathlove Oct 11 '14 at 22:13
  • $\begingroup$ @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. $\endgroup$ – 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}.$$

  • $\begingroup$ can you please explain a little bit more on how did you get the $2^n + 2^n$? $\endgroup$ – FarahFai Oct 11 '14 at 21:58
  • $\begingroup$ 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. $\endgroup$ – rogerl Oct 11 '14 at 21:59

The inductive step

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


Not the answer you're looking for? Browse other questions tagged or ask your own question.