Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

5 Answers 5

up vote 3 down vote accepted

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!

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer
    
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. –  Chris's sis 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$.

share|improve this answer

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

share|improve this answer
1  
$(\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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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