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.

Prove that $$\frac{n^n}{3^n} < n! < \frac{n^n}{2^n} \forall n \geq 6 $$

I'm trying induction, this is what I have so far:

Basecase $(n=6): 64<720<729$ is true.

Inductive Case: Assume the inequality $\frac{n^n}{3^n} < n! < \frac{n^n}{2^n} $ holds $ \forall n $ such that 6 $\leq n \leq k $, want to show that the inequality will hold for $n=k+1$.

What next?

share|improve this question
2  
For the left side you may use the fact that $e^n> \frac{n^n}{n!}$. This is easy to note from Taylor expansion of $e^x$. –  Chris's sis Sep 9 '12 at 21:12
1  
For the right side note that $(\frac{n!}{n^n})^{1/n}$ is strictly decreasing if you take into account the values for $n\ge2$ and its limit is $\frac{1}{e}$. Hence, the proof is complete. –  Chris's sis Sep 9 '12 at 21:23
add comment

4 Answers

up vote 5 down vote accepted

From $\exp(x)=\sum_{n=0}^\infty \frac{x^n}{n!}> \frac{x^n}{n!}$ for $x>0$ you get immediately that $\exp(n)> \frac{n^n}{n!}$. Knowing that $e<3$ we conclude $3^n>\exp(n)>\frac{n^n}{n!}$, hence the left inequality.

When the right hand side grows from $\frac{n^n}{2^n}$ to $\frac{(n+1)^{n+1}}{2^{n+1}}$ this is by a factor of $$ \frac{(n+1)^{n+1}}{2n^n}=\frac{n+1}2 \frac{(n+1)^{n}}{n^{n}}=\frac{n+1}2 \left(1+\frac1n\right)^{n}$$ The term $\left(1+\frac1n\right)^n$ should be well-known to converge monotonically $\to e$ from below. Especially, $\frac{n+1}2 \left(1+\frac1n\right)^{n}>n+1$, i.e. the right hand side grows faster than the middle term.

share|improve this answer
1  
The inequality $(1+1/n)^n \geq 2$ can be seen more simply by looking at the first two terms in the expansion. –  Sean Eberhard Sep 9 '12 at 22:09
add comment

Hint: You have two things to prove: one is $\frac {(k+1)^{(k+1)}}{3^{(k+1)}}\lt (k+1)!$. Try to write these terms in terms of what you know about $k$, so the right side is clearly $(k+1)k!$. We can then say $(k+1)k!\gt (k+1)\frac {k^k}{3^k}$. You need to relate $(k+1)^{(k+1)}$ and $k^k$, so need to say something about $(1+\frac 1k)^k.$ Does that ring a bell?

share|improve this answer
    
What I don't get is how to get the k^k part all by itself. What am I missing? I mean I understand you can break down (k+1)^(k+1) into (k+1)^k*(k+1), but how do you get k^k so you can use the inductive hypothesis? –  user39794 Sep 9 '12 at 21:20
    
How did you get $(k+1)$ $\dfrac{k^k}{3^k}$ from $\dfrac{(k+1)^{k+1}}{3^{k+1}}$ –  CodeKingPlusPlus Sep 21 '12 at 1:16
    
@CodeKingPlusPlus: I used the induction hypothesis, which here says $k! \gt \frac{k^k}{3^k}$ From that we need to prove that $(k+1)! \gt \frac {(k+1)^{(k+1)}}{3^{(k+1)}}$. Then you observe that $\frac ({k+1)^k}{3k^k} \lt 1$ so you can make one more link in the chain and you are there. That was the point of my next to last sentence. The fraction is about $\frac e3$. –  Ross Millikan Sep 21 '12 at 1:31
    
math.stackexchange.com/questions/200055/… --This link is what I came up with. Please visit it and write a comment about the work I show. –  CodeKingPlusPlus Sep 21 '12 at 2:11
add comment

Hint: for the left side use the fact that $\displaystyle e^n> \frac{n^n}{n!}$ that comes from Taylor expansion if you take out all terms except the last one. For the right side note that $\displaystyle(\frac{n!}{n^n})^{1/n}$ is decreasing from $n\ge2$. Hence with a bit of work from your side you're done.

share|improve this answer
    
I get it now, thank you all very much! –  user39794 Sep 9 '12 at 21:36
    
@Allison Cameron: you're welcome :-) –  Chris's sis Sep 9 '12 at 21:39
add comment

Given:

$$\frac{n^n}{3^n} < n! < \frac{n^n}{2^n} \forall n \geq 6$$

Using Sterling's formula we want to prove the following 2 inequalities:

$$\frac{n^n}{3^n} < \sqrt{2\pi n}\left ( \frac{n}{e} \right )^n ---> [1] $$

and

$$\frac{n^n}{2^n}>\sqrt{2\pi n}\left ( \frac{n}{e} \right )^n ---> [2] $$

For the first inequality suppose that the opposite is true; that is, suppose that:

$$\frac{n^n}{3^n} \geq \sqrt{2\pi n}\left ( \frac{n}{e} \right )^n ---> [3] $$

so, $$n^n \geq \sqrt{2\pi n}\left ( \frac{3*n}{e} \right )^n$$

since $3/e$ is about $1.10363832351$ we'd have:

so, $$n^n \geq \sqrt{2\pi n}\left ( 1.01*n \right )^n$$

The above is clearly not true for any value of $n \geq 6$. Hence the proposition in [3] is false and [1] is true.

The same idea can be used to prove iniquality [2]. Note that $2/e$ is approximately 0.73575888234.

share|improve this answer
add comment

Your Answer

 
discard

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