4
$\begingroup$

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

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

$\endgroup$
2
  • 2
    $\begingroup$ For what $n$ are you claiming this to be true? $\endgroup$
    – John M
    Aug 20 '13 at 18:37
  • $\begingroup$ 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? $\endgroup$ Aug 20 '13 at 19:36
5
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Why the second equation? $\endgroup$
    – Norza
    Aug 20 '13 at 19:03
  • 2
    $\begingroup$ 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$) $\endgroup$ Aug 20 '13 at 19:05
  • $\begingroup$ 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. $\endgroup$
    – Peng
    Aug 20 '13 at 19:08
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – user84413
    Aug 21 '13 at 17:15
  • $\begingroup$ 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... $\endgroup$ Aug 21 '13 at 17:22
  • $\begingroup$ Thanks for your reply, and it was helpful to me to see how you had rearranged the inequality to relate it to other limits. $\endgroup$
    – user84413
    Aug 21 '13 at 17:27
  • $\begingroup$ 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. $\endgroup$
    – Norza
    Aug 22 '13 at 17:15

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