Prove $2^n \lt\ n!$

Question

Prove by induction: $A(n) = 2^n \lt\ n!$

$A(n+1) = 2^{n+1} \lt\ (n+1)!$

The expression below is true for $n = 5$.

$2^n \lt\ \frac{n!}{2}$

Then, we have:

$2^n \lt\ \frac{n!}{2} \lt\ n! \lt\ (n+1)!$

Which implies that:

$2^{n+1} \lt\ (n+1)!$ for every $n \ge\ 5$

Is this proof correct?

Update: the case is true for $n = 4$. It's true for $n = 5$, too. I started the induction proof with $n = 5$.

Let be more clear:

$A(n) = 2^n \lt\ n!$ is true for $n = 5$.

For $n= 5$, the expression $2^n \lt\ \frac{n!}{2}$ is true too.

From the expression above, we can deduce: $$2^n \lt\ \frac{n!}{2} \lt\ n! \lt\ (n+1)!$$

$$2^n * 2 \lt\ n! \lt\ (n+1)!$$ Hence: $$2^{n+1} \lt\ (n+1)!$$

I would like to know if there is something wrong with this proof. Remember, I assumed the expression is true for $n=5$, not $n=4$ (which is true too).

Update 2: I think is neccessary to prove the expression below by induction first:

"For $n= 5$, the expression $2^n \lt\ \frac{n!}{2}$ is true too."

We don't know if it's true for $ n\gt\ 5$

Answer 1

Since you are asking specifically for whether or not your proof is correct, I have to say...if I were the one grading your work, then I would probably give it 5/10 or 6/10. Why? Well, it seems you are missing the main point concerning proofs by induction. That is, you need to

1. Prove that your result is true for some specific number $n=\,?$ (this is the base case).
2. Fix some $k\geq\,?$ and assume (this assumption is the inductive hypothesis) that your statement holds for $k$. Then you show that, based on your assumption, your statement is also true for $k+1$.

You really should read this post in the future on how to write up clear induction proofs. To that end, consider the following, which is the core part of the inductive argument.

---

\begin{align} 2^{k+1}&= 2\cdot2^k\tag{exponent rule}\\[1em] &< 2\cdot(k!)\tag{by inductive hypothesis}\\[1em] &< (k+1)\cdot k!\tag{$k\geq4\implies2<k+1$}\\[1em] &= (k+1)!\tag{factorial definition} \end{align} All of the other "stuff" you can write out in that template I linked to, but the above part is the main argument.

Answer 2

For $n=4$ we have

$$2^4<4!$$

Now, assume for some $k>4$ we have $$2^k<k!$$

Then, note that

$$\begin{align} 2^{k+1}&=2\times 2^k\\\\ &<2\times k!\\\\ &<(k+1)k!\\\\ &=(k+1)! \end{align}$$

And we are done!

Answer 3

How to structure a proof by induction:

Base case: $n=4$

$2^4 < 4!$

Inductive hypothesis: $2^n < n!$

Show that: $2^{n+1}<(n+1)!$ based on the inductive hypothesis.

$2^{n+1} = 2 \cdot 2^{n}<2\cdot 2 (n!) < (n+1)!$

For all $n\ge 4, 2^n < n!$

Answer 4

Claim: $2^n < n!$ for $n\geq 4$.

Base case: $2^4 < 4! \implies 16 < 24$, which is true.

Inductive step: Assume that $2^n < n!$ for some $n \geq 4$. Show that $2^{n+1} < (n+1)!$ as follows:

$2^n < n!$

$2^n \cdot 2 < n! \cdot 2$

and since $n! \cdot 2 < n! \cdot (n+1)$, we have

$2^n \cdot 2 < n! \cdot (n+1)$

$2^{n+1} < (n+1)!$