Prove by induction that $n! > 2^n$

117 Views Asked by At

Suppose that when $n=k$ $(k\geq4)$, we have that $k!>2^k$.

Now, we have to prove that $(k+1)!\geq2^{k+1}$ when $n=(k+1)$ $(k\geq4)$.

$$(k+1)! = (k+1)k! > (k+1)2^k \text{ (since }k!>2^k)$$

That implies $(k+1)!>2^k2$, since $(k+1)>2$ because of $k$ is greater than or equal to 4.

Therefore $(k+1)!>2^{k+1}$

Finally we may conclude that $n!>2^n$ for all integers $n\geq4$


Solved, thank you!

2

There are 2 best solutions below

0
On

As KyleW points it, this should hopefully not go off as an unanswered question, particularly if you feel like you have figured it out / solved it. Thus, consider my proof below to complement or complete your own.

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

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

Inductive step: Fix some $k\geq 4$ and assume that $$ S(k) : 2^k <k! $$ is true. It remains to show that $$ S(k+1) : 2^{k+1} < (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] &<2\cdot k!\tag{by $S(k)$, the inductive assumption}\\[0.5em] &<(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$

0
On

If $n\ge4$, then $n! = n\cdot (n-1) \cdots 5 \cdot 4! \ge 2 \cdot 2 \cdots 2\cdot 2^4 = 2^{n-4} \, 2^4 = 2^n$.

This argument actually proves that $n! \ge 4^{n-4}\, 2^4 = 4^{n-2}$, for $n\ge 4$, which is better but not as nice.

(Induction is hidden, as always, in the dots. Here, it is in $x_1, \dots, x_m \ge a \implies x_1 \cdots x_m \ge a^m$.)