Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
add comment

2 Answers

up vote 1 down vote accepted

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?

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.