i am asked to prove this statement:


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

  • 1
    $\begingroup$ $\left(\frac{1}{3}\right)^n \leq \frac{1}{3}$ $\endgroup$ – mrs 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$.


  • $\begingroup$ wow, amazing power of maths!! thanks a lot $\endgroup$ – doniyor Dec 24 '12 at 13:51
  • $\begingroup$ @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. $\endgroup$ – 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$$


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

  • $\begingroup$ This is a nice way. But the question has $3^{n-1}$ $\endgroup$ – Amr Dec 24 '12 at 10:27
  • $\begingroup$ Unless you meant that for sufficently large $n$, we have $e^n<3^{n-1}$ .Nice answer +1 $\endgroup$ – Amr Dec 24 '12 at 10:29
  • $\begingroup$ @Amr: this is correct. Thanks. $\endgroup$ – user 1357113 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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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