# how to prove $\left(\frac{n}{3}\right)^n\leq\frac{1}{3}n!$

i am asked to prove this statement:

$$\left(\frac{n}{3}\right)^n\leq\frac{1}{3}n!$$

Now after several attempts, i am lost not knowing where and how to start. if I use induction, i am stuck on the way. how can i solve this in an easy way? i have huge difficulties when i have to find something which is bigger than the latter term or so, because i lack some important source of maths in my brain. i am very likely to give up on the way if it becomes tough. for any guidance how to overcome this phase i will be very very thankful. i am trying for proficiency in math. Thanks

-
$\left(\frac{1}{3}\right)^n \leq \frac{1}{3}$ – Babak S. Dec 24 '12 at 9:56

We would like to prove

$$\left(\frac{n}{3}\right)^n \leq \frac{1}{3}n!.$$

This is equivalent to

$$n^{n-1} \leq 3^{n-1}(n-1)!.$$

It is obviosly true for $n = 1$. However, as $n$ increases, left side rises slower that the right-hand side (thus the inequality will still hold). To put this formally, consider the ratio

$$\frac{(n+1)^{n}}{(n)^{n-1}} \leq \frac{3^{n}n!}{3^{n-1}(n-1)!} = 3n$$

which simplifies to

$$\left(\frac{n+1}{n}\right)^{n} \leq 3.$$

and is true because $\left(1+\frac1n\right)^n$ is increasing in $n$ (e.g. see this post) and converges to $e < 3$.

Cheers!

-
wow, amazing power of maths!! thanks a lot – doniyor Dec 24 '12 at 13:51
@doniyor Observe that you could easily substitute 3 with $e$. Moreover with similar technique you could derive the inverse bound $\frac{1}{2}n! \leq \left(\frac{n}{2}\right)^n$. Check also the Wikipedia. – dtldarek Dec 24 '12 at 14:57

$$\left(\frac{n}{3}\right)^n\leq\frac{n!}{3}\Longleftrightarrow X_n:=\frac{n^n}{3^{n-1}n!}\leq 1$$

But

$$\frac{X_{n+1}}{X_n}=\frac{(n+1)^{n+1}}{3^n(n+1)!}\cdot\frac{3^{n-1}n!}{n^n}=\left(1+\frac{1}{n}\right)^n\frac{1}{3}\xrightarrow [n\to\infty]{}\frac{e}{3}<1$$

So that the infinite positive series $\,\displaystyle{\sum_{n=1}^\infty X_n}\,$ converges and thus $\,X_n\xrightarrow[n\to\infty]{}0\Longrightarrow X_n<1\,$ , at least

from a certain index $\,n\,$ on.

-

If we consider the last term in the Taylor expansion of $e^x$, we have $$e^x\ge\frac{x^n}{n!}$$ and let $x=n$ that yields $$e^n\ge\frac{n^n}{n!}$$ and the conclusion follows.

-
This is a nice way. But the question has $3^{n-1}$ – Amr Dec 24 '12 at 10:27
Unless you meant that for sufficently large $n$, we have $e^n<3^{n-1}$ .Nice answer +1 – Amr Dec 24 '12 at 10:29
@Amr: this is correct. Thanks. – user 1618033 Dec 24 '12 at 10:37

Using logarithms, the inequality $\left( \frac{n}{3} \right)^n \leq \frac{1}{3} n!$ is equivalent to $\sum\limits_{k=1}^{n-1} \ln \left( \frac{3k}{n} \right) \geq 0$. But $$\sum\limits_{k=1}^{n-1} \ln \left( \frac{3k}{n} \right) \geq 1+ \int_1^{n-1} \ln \left( \frac{3x}{n} \right) dx = 1+ (n-1) \ln \left( \frac{3(n-1)}{ne} \right) >0$$ for $n >5$.

-

First we'll prove that

$(\frac{k+1}{3})^k\leq k!\Leftrightarrow (k+1)^k\leq 3^k k!$

base of the induction: for $k=0$ it is true

If it's true for $k$ we'll prove it is true for $k+1$: that is $3^{k+1}(k+1)!\geq (k+2)^{k+1}$.

$3^{k+1}(k+1)!=3(k+1)3^{k}k!\geq 3(k+1)(k+1)^k=3(k+1)^{k+1}\geq (k+2)^{k+1}$.

Since $3(k+1)^{k+1}\geq (k+2)^{k+1}\Leftrightarrow log 3(k+1)^{k+1}\geq log (k+2)^{k+1} \Leftrightarrow (k+1)log 3(k+1)\geq (k+1) log(k+2)\Leftrightarrow log\frac{3k+3}{k+2}\geq 0$.

which is true

For the main conclusion now:

For $n=0$ it is true.

suppose it is true for $n=k$

$(\frac{k}{3})^k\leq \frac{1}{3}k!$

we'll prove it is true for $n=k+1$

$(\frac{k+1}{3})^{k+1}=(\frac{k+1}{3})^k\cdot\frac{k+1}{3}\leq k!\cdot \frac{1}{3} (k+1) =\frac{1}{3}(k+1)!$

By induction it is true for all $n\in\mathbb{N}$.

-
$(\frac{k+1}{3})^k\cdot\frac{k+1}{3}\leq (\frac{k}{3})^k\cdot\frac{k+1}{3}$? Am I missing something? – Nameless Dec 24 '12 at 10:11
I think all the details are ok now... I really needed that cup of coffee – epsilon Dec 24 '12 at 11:21