Prove by induction $\frac{n^n}{3^n}<n!<\frac{n^n}{2^n}$ [closed]

$\dfrac{n^n}{3^n}<n!<\dfrac{n^n}{2^n}$

The case $n!<\dfrac{n^n}{2^n}$ is easier.

You want to prove that

$$\frac{(n+1)^n(n+1)}{3^n3}<(n+1)!$$

which, by induction assumption, would follow from the following fact

$$\frac{(n+1)^n}{3}<n^n.$$

Notice that this would again follow from

$$(1+\frac{1}{n})^n<3.$$

This, on the other hand, would be a natural consequence that $e=2.71...<3$.

1) Show that $n!<\frac{n^n}{2^n}$ for $n\ge6$

a) This is true for $n=6$, since $6!=720<729=3^6$.

b) Assume that $n!<\frac{n^n}{2^n}$ for some integer $n\ge6$.

Then $(n+1)!=(n+1)n!<(n+1)\cdot\frac{n^n}{2^n}$, and

$\frac{(n+1)^n}{n^n}=\big(\frac{n+1}{n}\big)^n=\big(1+\frac{1}{n}\big)^n\ge1+n(\frac{1}{n})=2$ by Bernoulli's inequality;

so $(n+1)\cdot\frac{n^n}{2^n}=\frac{(n+1)^{n+1}}{2^n}\cdot\frac{n^n}{(n+1)^n}\le\frac{(n+1)^{n+1}}{2^n}\cdot\frac{1}{2}=\frac{(n+1)^{n+1}}{2^{n+1}}$

and therefore $(n+1)!<\frac{(n+1)^{n+1}}{2^{n+1}}$.

2) Show that $\frac{n^n}{3^n}<n!$ for all integers $n\ge1$:

a) This is true for $n=1$, since $\frac{1}{3}<1$.

b) Assume that $\frac{n^n}{3^n}<n!$ for some integer $n\ge1$.

Then $(n+1)!=(n+1)n!>(n+1)\cdot\frac{n^n}{3^n}$, and

since $\frac{(n+1)^n}{n^n}=\big(1+\frac{1}{n}\big)^n<3$, as we will show below,

$(n+1)\cdot\frac{n^n}{3^n}=\frac{(n+1)^{n+1}}{3^n}\cdot\frac{n^n}{(n+1)^n}>\frac{(n+1)^{n+1}}{3^n}\cdot\frac{1}{3}=\frac{(n+1)^{n+1}}{3^{n+1}}$;

so $(n+1)!>\frac{(n+1)^{n+1}}{3^{n+1}}$.

To show that $\big(1+\frac{1}{n}\big)^n<3$ for all n, we have

$\big(1+\frac{1}{n}\big)^n=\sum_{k=0}^{n}\binom{n}{k}(\frac{1}{n})^k=\sum_{k=0}^{n}\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!\cdot n^k}\le\sum_{k=0}^{n}\frac{1}{k!}$, so

$\big(1+\frac{1}{n}\big)^n\le1+1+\frac{1}{2!}+\frac{1}{3!}+\frac{1}{4!}+\cdots\frac{1}{n!}\le1+1+\frac{1}{2!}+\frac{1}{3\cdot 2!}+\frac{1}{3^{2}\cdot 2!}+\cdots\frac{1}{3^{n-2}\cdot2!}=$

$\;\;\;\;\;\;\;2+\frac{\frac{1}{2}}{1-\frac{1}{3}}\big(1-(\frac{1}{3})^{n-1}\big)=2+\frac{3}{4}\big(1-(\frac{1}{3})^{n-1}\big)<2+\frac{3}{4}<3.$

Another way this might be viewed is by rearranging the inequalities as

$$2^n \ < \ \frac{n^n}{n!} \ \ \text{and} \ \ \frac{n^n}{n!} \ < \ 3^n , $$

the entirety of which holds for $ \ n \ = \ 6 \ , $ as already mentioned by user84413 . The "induction step" for the ratio is then

$$\frac{(n+1)^{n+1}}{(n+1)!} \ = \ \frac{(n+1)}{(n+1)} \ \cdot \ \frac{(n+1)^{n}}{n!} \ = \ \left( \frac{n+1}{n} \right)^n \ \cdot \ \frac{n^{n}}{n!} \ . $$

We know that this first factor produces a number between 2 and 3 for $ \ n \ \ge \ 1 \ $ (in fact, it's a familiar statement that $ \ \lim_{n \rightarrow \infty} \ \left( \frac{n+1}{n} \right)^n = \ e \ )^{*} \ , $

$^{*}$ indeed, some regard this as the defining equation for $ \ e \ $

so we can write

$$2^{n+1} \ = \ 2 \ \cdot \ 2^n \ < \ 2 \ \cdot \frac{n^n}{n!} \ \le \ \left( \frac{n+1}{n} \right)^n \ \cdot \ \frac{n^{n}}{n!} \ = \ \frac{(n+1)^{n+1}}{(n+1)!} \ $$

[the equation being true for $ \ n = 1 \ $ ]

and

$$ \frac{(n+1)^{n+1}}{(n+1)!} \ = \ \left( \frac{n+1}{n} \right)^n \ \cdot \ \frac{n^{n}}{n!} \ < \ 3\ \cdot \frac{n^{n}}{n!} \ < \ 3 \ \cdot \ 3^n \ = \ 3^{n+1} \ . $$

Thus, for $ \ n \ \ge \ 6 \ , $ we find $ \ 2^n \ < \ \frac{n^n}{n!} \ < \ 3^n \ , \ $ equivalent to the original inequality

$$ \ \frac{n^n}{3^n} \ < \ n! \ < \ \frac{n^n}{2^n} \ . \ $$

$$\\$$

Note that in so doing, we have also proven that $ \ \left(\frac{1}{3}\right)^n < \ \frac{n!}{n^n} \ < \ \left(\frac{1}{2}\right)^n \ , \ $ and hence, by the "Squeeze Theorem", that $ \ \lim_{n \rightarrow \infty} \ \frac{n!}{n^n} \ = \ 0 \ . $ The induction work is similar to that required in applying the Ratio Test to demonstrate the absolute convergence of $ \ \sum_{n=1}^{\infty} \ \frac{n!}{n^n} \ $ (and so also the divergence of $ \ \sum_{n=1}^{\infty} \ \frac{n^n}{n!} \ ) \ . $

ADDENDUM: It might seem, from the preceding discussion, that we ought to get something like an equation out of this by just using $ \ e \ $ ; but, in fact we find that $ \ \frac{n^n}{e^n} < \ n! \ . \ $ This touches on the Stirling approximation, which requires some additional non-linear factors in order to get closer to accurate values of $ \ n! \ $ for large $ \ n \ . $