1
$\begingroup$

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!

  • 0
    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).2012-02-19

2 Answers 2

1

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?

  • 0
    @cssl: It’s mostly straight $\LaTeX$, for which there are many guides and tutorials on the net. [Here](http://amath.colorado.edu/documentation/LaTeX/Symbols.pdf) 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.2012-02-19
0

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

  • 0
    @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.2012-02-19