Proof by contradiction that $n!$ is not $O(2^n)$ 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.
 A: First, observe that when $n = 4$, $4! = 24$ and $2^4 = 16$. Since $f(n)$ is $O(g(n))$ when there exists positive constants $c$ and $n_0$ such that $f(n) \leq cg(n)$ for all  $n > n_0$. That means $n!$ is $O(2^n)$ when there exists constant $c$ and $n_0$ such that $n! \leq c2^n$ for all  $n > n_0$. 
Knowing the MacLaurin series:$$\sum_{n=0}^{\infty} \frac{x^n}{n!} = e^x$$
As such: $\sum_{n=0}^{\infty} \frac{2^n}{n!} = e^2$. Therefore members of the sequence $\frac{2^n}{n!} \xrightarrow{}0 $. From there, the reciprocal is the sequence $\frac{n!}{2^n} \xrightarrow{} \infty $.
As such, the left side of $\frac{n!}{2^n} \leq c$ is growing infinitely with increasing $n$, therefore $c$ and $n_0$ has to increase with respect to $n$, but that won't satisfy for all $n > n_0$,  as such the Big-$O$ doesn't stand (proof by contradiction).
A: 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.
A: 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)$.
A: 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?
A: 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...
A: Suppose
$n! = O(2^n)$.
Then there is an integer
$N$ and a positive real $c$
such that
$n! < c 2^n$
for $n > N$,
or
$r_n
=\frac{2^n}{n!} 
> \frac1{c}$.
Let
$M = \max(N, 4)$.
If $n > M$,
$r_{n+1}
=\frac{2^{n+1}}{(n+1)!}
=\frac{2}{n+1}\frac{2^n}{n!}
< \frac12 r_n
$.
Therefore
$r_{n+k} < \frac{r_n}{2^k}$.
Note:
To show $\frac1{2^k}
\to 0$,
by Bernoulli's inequality,
$2^n
=(1+1)^n
> n
$.
A: This is the cleanest proof I can think of:
Using the same techniques used to show $2^n=O(n!)$, we can show that $3^n = O(n!)$ as well.  If we had $n!=O(2^n)$, then this implies $3^n = O(2^n)$, contradiction.
