I have a problem that I have to solve using mathematical induction but I'm stuck from a part. The problem is:

Proof that $\large n<2^n$ is true for $\large n \in \mathbb{N}\ $

So, I did that steps:

1) $n = 1$, $\qquad$ $1<2^1$ $\rightarrow$ $1 < 2$ $\qquad$ THIS IS TRUE

2) $n = k$, $\qquad$ $k < 2^k$

3) $n = k+1$, $\qquad$ $k+1 < 2^{k+1}\ $

$\qquad$$\qquad$$\qquad$$\quad$ $k < 2^k$

$\qquad$$\qquad$$\qquad$$\quad$ $2 * k < 2^k * 2$ $\qquad$ I multiplied by $2^1$ in both sides to get

$\qquad$$\qquad$$\qquad$$\quad$ $2k < 2^{k+1}$

I'm stuck in this part, what should I do next?? Please be specific

  • $\begingroup$ If $k>1$ then $k+1<k+k=2k$, so ... $\endgroup$ – DiegoMath Sep 7 '14 at 6:38

When you have $k<2^k$ (2) then $k+\color{red}1<2^k+\color{red}1$. But $$\color{red}1< \color{green}{2^k},~~\forall k\in\mathbb N.$$ so you get $$k+\color{red}1<2^k+\color{red}1<2^k+\color{green}{2^k}.$$


For $n=1$ we have $$1 < 2.$$ From $n=k$ to $n=k+1$ note that $k < 2^{k}$ is equivalent to $k+1 \leq 2^{k},$ so that $$k+1 \leq 2^{k} < 2^{k+1}$$ follows.


I think you should have done it like this

By assumption:


         2(k+1)<2*2^k            * by 2 both sides

since 2*2^k>2(k+1)

and 2(k+1)>k+1

  for example if n>10

  therefore     n>5

Therefore k+1<2*2^k



Then statement n<2^n is valid for all Natural Numbers


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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