6
$\begingroup$

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

  • 1
    $\left(\frac{1}{3}\right)^n \leq \frac{1}{3}$2012-12-24

5 Answers 5

1

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

  • 0
    I think all the details are ok now... I really needed that cup of coffee2012-12-24
4

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

4

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.

  • 0
    @Amr: this is correct. Thanks.2012-12-24
3

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!

  • 0
    @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](http://en.wikipedia.org/wiki/Factorial).2012-12-24
2

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