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