I'm having difficulty solving an exercise in my course.
The question is:
Prove that $n!\geq 2^n$.
We have to do this by induction. I started like this:
- The lowest natural number where the assumption is correct is $4$ as: $4! \geq 2^4 \iff 24 \ge 16$.
- The assumption is: $n! \ge 2^n$.
Now proof for $(n+1)$ which brings me to: $(n+1)! \ge 2^{(n+1)}$
I think I can rewrite it somehow like this:
$$ {(n+1)} \times {n!} \stackrel{\text{(definition of factorial)}}{\ge} 2^n \times 2 $$
$$ (n+1) \times 2^n \ge 2^n \times 2 $$
Then I think I can eliminate the $2^n$ and have something like this: $n+1 \ge 2$, or $n \ge 1$.
But I think I'm wrong here some where and was hoping somebody has some advice on this. How can I prove the above assumption?
Any help would be appreciated, kind regards.
In the induction step you want to show that if $k!\ge 2^k$ for some $k\ge 4$, then $(k+1)!\ge 2^{k+1}$. Since you already know that $4!\ge 2^4$, the principle of mathematical induction will then allow you to conclude that $n!\ge 2^n$ for all $n\ge 4$. You have all of the necessary pieces; you just need to put them together properly. Specifically, you can argue as follows.
Suppose that $k!\ge 2^k$, where $k\ge 4$; this is your induction hypothesis. Then $$\begin{align*} (k+1)! &= (k+1)k!\text{ (by the definition of factorial)}\\ &\ge (k+1)2^k\text{ (by the induction hypothesis)}\\ &> 2\cdot2^k\text{ (since }k\ge 4\text{)}\\ &= 2^{k+1}. \end{align*}$$ This completes the induction step: it shows that if $k\ge 4$, then $$k!\ge 2^k \implies (k+1)!\ge 2^{k+1}.$$