prove big-$O$ relation with Stirling's formula and limit theorem I need to disprove $n!=O(2^n)$ by using limits.
I have found by Stirling's formula $n!$ is $$(2\pi n)^{1/2}\left(\frac{n}e\right)^n\;.$$
I was trying to do 
$$\lim_{n\to\infty} {\frac{(2\pi n)^{1/2}\left(\frac{n}e\right)^n}{2^n}}\;.$$
But, this become extremely tedious and does not seem like a proper way..
Can some one give a hand on this?
I have no clue where to go..
Thanks！
 A: It isn’t actually true that $$n!=(2\pi n)^{1/2}\left(\frac{n}e\right)^n\;:$$ the righthand side is only approximately equal to $n!$. What is true, however, is that $$\lim_{n\to\infty}\frac1{n!}\cdot(2\pi n)^{1/2}\left(\frac{n}e\right)^n=1\;,\tag{1}$$ which would be good enough for your purposes if you were to approach the problem using Stirling’s approximation. That, however, is doing it very much the hard way. Here’s a much easier approach.
You want to show that $$\lim_{n\to\infty}\frac{n!}{2^n}=\infty\;.$$ The fraction has $n$ factors in both the numerator and the denominator, so you can write it as $$\frac{n!}{2^n}=\prod_{k=1}^n\frac{k}2=\frac12\cdot\frac22\cdot\frac32\cdot\ldots\cdot\frac{n-1}2\cdot\frac{n}2\;.$$ Call this product $f(n)$. By actual calculation $f(4)=3/2$. Now suppose that $n>4$; then 
$$f(n)=f(4)\prod_{k=5}^n\frac{k}2=\frac32\cdot\underbrace{\frac52\cdot\frac62\cdot\ldots\cdot\frac{n-1}2\cdot\frac{n}2}\;.$$ Can you see why this is greater than $2^{n-4}$, and why that gives you the desired result?
A: By considering Taylor series we know that for $x\geq 0$ we have  $\displaystyle e^x \geq \frac{x^n}{n!} $ for all $ n \in \mathbb{N}.$ Letting $x=n$ gives $$ n! \geq \left( \frac{n}{e} \right)^n .$$
Thus, $$ \frac{n!}{2^n} \geq \left( \frac{n}{2e} \right)^n \to \infty $$
and thus $ n! \notin \mathcal{O}(2^n).$

Well that was overkill as well. The ratio of consecutive terms in the sequence is $$ \frac{(n+1)!}{2^{n+1}} \cdot \frac{2^n}{n!} = \frac{n+1}{2} > 2 $$ for all $n>3.$ Thus $\displaystyle  \frac{n!}{2^n} $ grows faster than a divergent geometric sequence. In fact, this argument still gives $ n! \notin \mathcal{O}(k^n) $ for any $k > 0.$
