Proof by induction the following: $n+1 ≤ 2^n ≤ (n+1)!$

Question

I've done the basis step for $n=1$ and managed to arrange the $n=k+1$ to: $(k+1) + 1 ≤ 2\cdot2^k ≤ (k+1)!(k+2)$

Not sure how to proceed from here?

Answer 1

You have: $2\cdot 2^k \geq 2(k+1) = 2k+2 \geq k+2$, and $2\cdot 2^k \leq 2\cdot (k+1)! \leq (k+2)(k+1)! = (k+2)!$

Answer 2

As suggested in the comments, you will need to separate each inequality and essentially do two proofs. To show the first inequality $n+1\le 2^n$ we start with the base case $n=1$:

$$ \begin{split} LHS&=n+1=1+1=2 \\ RHS&=2^n=2^1=2 \end{split} $$

So in this case $LHS\le RHS$ as required. Now assume that the inequality holds for some integer $k$, so $k+1\le 2^k$. We would like to show that this implies the result for $k+1$. When $n=k+1$ we get:

$$ \begin{split} LHS=(k+1)+1 &\le 2^k+1 \\ &\le 2^k+2^k \\ &=2\cdot 2^k \\ &=2^{k+1} =RHS \end{split} $$

So we have shown that the first inequality holds by induction.

For the second we do the same thing. For $n=1$:

$$ \begin{split} LHS&= 2^n=2^1=2 \\ RHS&=(n+1)!=(1+1)!=2!=2 \end{split} $$

Assume the result holds for some integer $k$, so $2^k\le (k+1)!$. Then for $n=k+1$:

$$ \begin{split} 2^{k+1}=2\cdot 2^k &\le 2\cdot (k+1)! \\ &\le (k+2)\cdot (k+1)! \\ &=(k+2)! \end{split} $$

as required. Hence both inequalities hold for $n\ge 1$.

Answer 3

Assume

$$k+1\le { 2 }^{ k }\le \left( k+1 \right) !$$ then you should prove that: $$\\ k+2\le { 2 }^{ k+1 }\le \left( k+2 \right) !$$

$$ k+1+1\le { 2 }^{ k }+1\le { 2 }^{ k }+{ 2 }^{ k }\le { 2 }^{ k }\cdot 2={ 2 }^{ k+1 }\\ { 2 }^{ k+1 }={ 2 }^{ k }\cdot 2\le 2\left( k+1 \right) !\le \left( k+2 \right) \left( k+1 \right) !=\left( k+2 \right) ! $$