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.

• For what $n$ are you claiming this to be true? Aug 20 '13 at 18:37
• Let $n = 1$. then $\frac {1^1}{3^1} < 1! < \frac {1^1}{2^1}$ Is obviously false. What $n$ is this statement valid for? Aug 20 '13 at 19:36

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

• Why the second equation? Aug 20 '13 at 19:03
• For the last inequality, note that $\left(1+\frac1n\right)^n<3\iff \left(1-\frac 1{n+1}\right)^n=\left(\frac n{n+1}\right)^n>\frac13$. Now use Bernoulli's inequality $(1+x)^n\ge 1+nx$ (for $x\ge -1, n\ge0$) Aug 20 '13 at 19:05
• The second equation is a consequence of the third equation. You start by proving the third one, then you have the second one, then you use the second one + induction assumption to have the first one.
– Peng
Aug 20 '13 at 19:08

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

• This is an interesting way to look at it. In claiming that $2<\bigg(\frac{n+1}{n}\bigg)^{n}<3$ for all $n\ge1$, though, I think you need that this sequence is increasing and that (by some other method) $2<e<3$. Aug 21 '13 at 17:15
• I'll agree that my argument is not completely rigorous. I believe it's not too hard to show that $\ \left( \ \frac{n+1}{n} \ \right)^n \$ is monotonically increasing. I think it is more difficult to be satisfied that 3 is an upper bound. My argument is really just a variation of yours, which I offered only to show that a rearrangement of the inequality might be easier to investigate... Aug 21 '13 at 17:22
• Thanks for your reply, and it was helpful to me to see how you had rearranged the inequality to relate it to other limits. Aug 21 '13 at 17:27
• Wow, very interesting perspective. Im writing notes for my computer science students and I had a proof for $n!<\frac{n^n}{2^n}$ but a very diffeerent one to the other inequality. The uniformity of your proofs and extra comments on $e$ are really useful. Thanks. Aug 22 '13 at 17:15