Prove that $2^n\le n!$ for all $n \in \mathbb{N},n\ge4$

Question

The problem i have is:

Prove that $2^n\le n!$ for all $n \in \mathbb{N},n\ge4$

Ive been trying to use different examples of similar problems like at:

http://web.cacs.louisiana.edu/~mgr/261/induction.html

First i show the base case $n=4$ is true.

Then assuming $2^k\le k!$ for some $k \in \mathbb{N},n\ge4$

For $k+1$ we have $2^{k+1}\le (k+1)!$

Rewritten as $2\cdot2^k\le k!\cdot(k+1)$

Can you not simply say $2^k\le k!$ from the inductive hypothesis, and $2\lt4\le k\lt k+1$ proving the induction step?

I am having trouble following some of what seems to me like unnecessary steps like in the example, but feel like what i did above is wrong as im of course just learning how to use induction.

Answer 1

With induction proofs, I would encourage you to clearly demarcate each step of your proof (i.e., where you show the base case to be true, where you make the induction assumption, where you use the induction assumption, etc.). That being said, see if you can follow the proof outlined below.

---

Claim: For $n\geq 4$, denote the statement involving $n$ by $$ S(n) : 2^n\leq n!. $$

Base step ($n=4$): $S(4)$ says that $2^4=16\leq 24=4!$, and this is true.

Inductive step: Fix some $k\geq 4$ and assume that $$ S(k) : 2^k\leq k! $$ is true. We must now show that $$ S(k+1) : 2^{k+1}\leq (k+1)! $$ follows. Beginning with the left-hand side of $S(k+1)$, \begin{align} 2^{k+1} &= 2\cdot 2^k\tag{by definition}\\[0.5em] &\leq 2\cdot k!\tag{by $S(k)$, the inductive assumption}\\[0.5em] &\leq (k+1)(k!)\tag{since $k\geq 4$}\\[0.5em] &= (k+1)!, \end{align} we end up with the right-hand side of $S(k+1)$, thus concluding the inductive step.

Thus, by mathematical induction, for all $n\geq 4$, the statement $S(n)$ is true. $\blacksquare$

Answer 2

Both sides are product of $n$ numbers: on the LHS it is 2 that is multiplied all the $n$ times. On the rhs every time it is a number that is bigger than the previous one that participates in the multiplication. Hence RHS will be bigger soon, which can be checked happens at $n=4$ first and then there is no turning back.

Answer 3

An easy and intuitive solution.
Write $k>3$ in place of $k\geq4$.
One can easily prove the base case.
Now Assume that $2^k\leq k!$
So lets prove that $2^{k+1}\leq (k+1)!$
$2^k.2\leq (k+1)k!$
Multiply both sides by $-1$ and flip the sign.
$-2^k.2> -(k+1)k!$
$k!\geq 2^k$ ->Assumption
So $-2^k.2> -(k+1)2^k$
$-2>-k-1$ Divide both sides by $2^k$ and flip the sign
So k>1
Hence proved.

Answer 4

A "graphical" approach:

We are comparing $$\overbrace{\overbrace{\overbrace{2\cdot 2\cdot 2}^{=2^3=8}\cdot 2}^{=2^4=16}\cdot 2 \cdot 2\cdot 2\cdot\ldots\cdot 2}^{=2^n} $$ with $$\underbrace{\underbrace{\underbrace{1\cdot 2\cdot 3}_{=3!=6}\cdot 4}_{=4!=24}\cdot 5 \cdot 6\cdot 7\cdot\ldots\cdot n}_{=n!} $$

$4!=24>16=2^4$

From the above, we can see that for $n> 4$, each additional term in $n!$ (i.e. each $n$) is greater than $2$.

Hence, for $n\geq4$, $$2^n<n!.$$

Answer 5

You can compare growth rates:

$$\frac{n!}{(n-1)!} = n,$$ $$\frac{2^n}{2^{n-1}} = 2 $$

This shows that for $n > 2$, as soon as $2^n \geq n!$, you'll have $2^N > N!$ for all $N > n$.

Sometimes it might be better to do $u_{n} - u_{n-1}$ instead of $\frac{u_n}{u_{n-1}}$.

You can also compare derivatives ($\frac{dy}{dx}$) or derivatives of logs ($\frac{d\log y}{dx}$).