Proof by contradiction that $n!$ is not $O(2^n)$

Question

I am having issues with this proof: Prove by contradiction that $n! \ne O(2^n)$. From what I understand, we are supposed to use a previous proof (which successfully proved that $2^n = O(n!)$) to find the contradiction.

Here is my working so far:

Assume $n! = O(2^n)$. There must exist $c$, $n_{0}$ such that $n! \le c \cdot 2^n$. From the previous proof, we know that $n! \le 2^n$ for $n \ge 4$.

We pick a value, $m$, which is gauranteed to be $\ge n_{0}$ and $\ne 0$. I have chosen $m = n_{0} + 10 + c$.

Since $m > n_0$:

$$m! \le c \cdot 2^m\qquad (m > n \ge n_0)$$

$$\dfrac{m!}{c} \le 2^m$$

$$\dfrac{1}{c} m! \le 2^m$$

$$\dfrac{1}{m} m! \le 2^m\qquad (\text{as }m > c)$$

$$(m - 1)! \le 2^m$$

That's where I get up to.. not sure which direction to head in to draw the contradiction.

Answer 1

If $n!=O(2^n)$, then there is a constant $c$ such that whenever $n>N$, then

$$n!\leq c\cdot 2^n$$

This means that whenever $n>N$,

$$\frac{n!}{2^n}\leq c$$

This means that the sequence $$a_n=\frac{n!}{2^n}$$

is bounded.

Don't you smell something fishy? I give you $m=1234966785$. Can you find $n'$ such that $a_{n'}>m$? Can you do this for any $m$ I give you?

Note that

$$a_n=\frac 1 2 \frac 2 2 \frac 3 2 \cdots \frac{n-1}{2}\frac n 2$$

Note that each term, except $\frac 1 2 $ greater or equal than $1$ for $n=1,2,\dots$ that is

$${a_n} = \frac{1}{2}\frac{2}{2}\frac{3}{2} \cdots \frac{{n - 1}}{2}\frac{n}{2} \geqslant \frac{1}{2}1 \cdot 1 \cdots 1 \cdot \frac{n}{2} = \frac{n}{4}$$

Then, this means $$b_n=\frac n 4 $$ is bounded. Do you see what's going on?

Answer 2

In Factorial Inequality problem $\left(\frac n2\right)^n > n! > \left(\frac n3\right)^n$, they have obtained $$ n!\geq \left(\frac{n}{e}\right)^n. $$ Hence $$ \lim_{n\rightarrow\infty}\frac{n!}{2^n}\geq\lim_{n\rightarrow\infty}\left(\frac{n}{2e}\right)^n=\infty. $$ Suppose that $n!=O(2^n)$. Then there exist $C>0$ and $N_0\in \mathbb{N}$ such that $$\frac{ n!}{2^n}\leq C $$ for all $n\geq N_0$. Lettting $n\rightarrow\infty$ in the aobve inequality we obtain $$ \lim_{n\rightarrow\infty}\frac{n!}{2^n}\leq C, $$ which is an absurd.

Answer 3

It is quite easy to show that $n! \ge 3^n$ if $n\ge 7.$ If $n = 7$, we have $3^7 = 2187 < 5040 = 7!$. Now let $n\ge 7$.
$$n! = n\cdot(n-1)! \ge 3\cdot(n-1)! = 3\cdot 3^{n-1}, $$ if we invoke the induction hypothesis $n! \ge 3^n$.
Then $${n!\over 2^n} \ge {3^n\over 2^n} \to \infty$$ as $n\to\infty$. This rules out $n! = O(2^n)$.

Answer 4

Something "fancy" here. Look at the positive series $$\sum_{n=1}^\infty \frac{2^n}{n!}$$

Of course, we know the above series has sum equal to $\,e^2\,$ , but what's important here is that it is seriously easy to prove the convergence of the series and thus $$\frac{2^n}{n!}\xrightarrow [n\to\infty]{} 0\Longrightarrow \frac{n!}{2^n}\xrightarrow [n\to\infty]{}\infty$$ and thus it's obvious the sequence cannot be bounded...