# 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！

-
I don't think you need to use anything as subtle as Stirling's formula for the problem you have been set, and it may be easier to deal with a simpler estimate. For example, you have something like $n! \geq (\frac{n}{2})^{\frac{n}{2}}$ (I think this is OK for odd $n$, but needs a little more care). –  Geoff Robinson Feb 19 '12 at 7:58

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?

-
i have stared at ur solution for long time..I don't see why is f(n)> 2n−4 and why need this..what i found is 2^n will always be canceled by some number less than n..Can you explain further? thanks –  cssl Feb 19 '12 at 8:56
@cssl: The smallest of those $n-4$ factors is $5/2$, so all of them are greater than $2$, and their product is therefore greater than $2^{n-4}$. $3/2>1$, so $f(n)>2^{n-4}$. Now what’s $\lim_{n\to\infty}2^{n-4}$? –  Brian M. Scott Feb 19 '12 at 9:03
infinity..finally i got this thanks.BTW how to type those math symbols?Is there a manual? –  cssl Feb 19 '12 at 9:14
@cssl: It’s mostly straight $\LaTeX$, for which there are many guides and tutorials on the net. Here is a handy basic guide. Also, if you right-click on an expression here and then click on ‘TeX Commands’ under ‘Show Math As’, you’ll get a pop-up window displaying the code that was used to produce the expression. –  Brian M. Scott Feb 19 '12 at 9:20

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.$

-
I kind lost here. I have no idea about taylor series..what sequence are u referring to? Sorry... –  cssl Feb 19 '12 at 8:38
@cssl It is okay if you haven't seen Taylor series before, the second solution is enough. As I was writing out a more explicit version of it in response to your comment, I realized an even stronger similarity to Brian's solution than I previously thought. Thus I suggest you try to read Brian's solution and carry out his instructions. –  Ragib Zaman Feb 19 '12 at 8:56