Proof by induction: $2^{n} < n!$

Question

Prove that $2^{n} < n!$ $\forall$ n > 4

$n=5:$ $$2^{5}<5!$$

$$32 < 120$$

This is true.

Now, after knowing it worked for $n$ we need to show it works for every other, so $n+1$:

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

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

We know from beginning that $2^{n} < n!$

So we replace it with it here and then show:

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

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

$$1<\frac{n+1}{2}$$

Task say for all $n > 4$ so the thing on the right side will really be greater than $1$.

---

I hope everything is ok?

Edit: The possible-duplicate-link didn't help me because I'm not really looking for a solution to the task. I'm rather interested in knowing if MY proof is correct.

Answer 1

I would simply note that for sufficiently large $n$, $2$ < $n$ + $1$. Then by induction, when $2^n$ < $n$!, $2^n$ ${\times}$ $2$ < $n$! ${\times}$ $2$ and $n$! ${\times}$ $2$ < $n$! ${\times}$ $n + 1$, so by transitivity $2^n$ ${\times}$ $2$ < $n$! ${\times}$ $n + 1$.

Answer 2

Are you stating that if $a<b$ and $a<c$ then $b<c?$ But you have the correct answer. I'd do it in this way.

Assume its true that it's true that $2^n<n!=>\frac{2^n}{n!}<1$ then for $n+1$ we have to prove that:

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

$2^n<n!(n+1) * 1/2$

$\frac{2^n}{n!}<(n+1)*1/2$

And then state that as $\frac{2^n}{n!}<1$ and $\frac{n+1}{2}>1$ for any $n>4$ Therefore the inequality is true.

Answer 3

Your results are indeed correct. The only thing is, whatever steps you wrote down, follow them in reverse order, i.e write the last step first and so on. Then, the proof will be a well-written inductive proof.(And it is a pretty good strategy to prove results, isn't it)?

Answer 4

Hint:

$$4<n\implies2^{n+1}=2^n\cdot2<n!\cdot2<(n+1)!$$

Answer 5

A precise proof is as follows:

For 4 ≤ n we have: $2$ < $n$ + $1$. Now using this and by induction, assuming $2^n$< $n$! we may simply get:

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

The above argument is just based on this basic fact that if a>b and c>d then a×c>b×d , for all positive integers. Note that this is true for 4 ≤ n.

Answer 6

In addition to my solution, I should note that there is a serious basic error in your proof. Note that you can NEVER use this formula $2^{n+1} < (n+1)!$ in any step in your proof procedure (by induction), as it should be merely gotten as the final consequence. As I've shown in the solution, we should necessary start with the initial assumptions which are: $2^4$< $4$! and $2$ < $n$ + $1$ (which is true for n ≥ 4).

Now as you see in the solution, by induction supposing $2^n$< $n$!, we can get strightforwardly:

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

as the main requirement. In general, there is a similar procedure in any proof by induction.