6
$\begingroup$

I need to prove for all positive integer $n$

$$ e\left(\frac{n}{e}\right)^n\leq n!\leq en\left(\frac{n}{e}\right)^n, $$ using the hint $1+x\leq e^x$ for all $x\in \mathbb{R}$.

I did this:

The hint says

  • for $x=0$, $1\leq 1$;
  • for $x=1$, $2\leq e$;
  • ...
  • for $x=n-1$, $n\leq e^{n-1}$.

So I multiplied these $n$ inequalities to get

$$ n!\leq e^{n-1+\ldots+1}, $$ or $$ n!\leq e^{\frac{n(n-1)}{2}}, $$ and I get stuck there.

$\endgroup$
  • $\begingroup$ I will edit to let $n$ be positive. $\endgroup$ – Zir Jan 15 '17 at 0:15
  • $\begingroup$ Oh, whoops, was I supposed to use $1+x\le e^x$? $\endgroup$ – Simply Beautiful Art Jan 15 '17 at 0:39
  • $\begingroup$ Yes, that was the hint I am supposed to use. $\endgroup$ – Zir Jan 15 '17 at 0:44
  • 1
    $\begingroup$ Bleh, well, whatever XD. $\endgroup$ – Simply Beautiful Art Jan 15 '17 at 1:33
6
$\begingroup$

Rearranging gives the equivalent inequalities $$1 \le (n-1)! \left(\frac{e}{n}\right)^{n-1} \le n.$$

When $n=1$ both inequalities are equalities. Assuming the statement holds for $n=k$, then we want to prove $$1 \le k! \left(\frac{e}{k+1}\right)^k \le k+1.$$


The first inequality holds since $$k! \left(\frac{e}{k+1}\right)^k = \underbrace{e \cdot \left(\frac{k}{k+1}\right)^k}_{\ge 1} \cdot \underbrace{(k-1)! \left(\frac{e}{k}\right)^{k-1}}_{\ge 1 \text{ by induction}}$$ where the first term is $\ge 1$ because the hint gives $$e^{1/k} \frac{k}{k+1} \ge \left(1+\frac{1}{k}\right) \frac{k}{k+1} = 1.$$


The second inequality is due to $$k! \left(\frac{e}{k+1}\right)^k = \underbrace{e \cdot \left(\frac{k}{k+1}\right)^k}_{\le \frac{k+1}{k}} \cdot \underbrace{(k-1)! \left(\frac{e}{k}\right)^{k-1}}_{\le k \text{ by induction}}$$ where the first term is $\le \frac{k+1}{k}$ because $$e \cdot \left(\frac{k}{k+1}\right)^{k+1} = e \cdot \left(1-\frac{1}{k+1}\right)^{k+1} \le e \cdot e^{-1} = 1.$$ [It is well known that $\left(1-\frac{1}{k+1}\right)^{k+1}$ converges to $e^{-1}$ as $k \to \infty$, but one can show by induction that this actually increases monotonically to $e^{-1}$.]

$\endgroup$
  • 2
    $\begingroup$ Thanks. In fact the last one is also due using the hint by setting $x=-\frac{1}{k+1}$ in $1+x\leq e^x$. $\endgroup$ – Zir Jan 15 '17 at 2:43
2
$\begingroup$

Take the log of all sides, so we just need to prove that

$$n\ln n-n+1\le\ln(n!)\le (n+1)\ln n-n+1$$

Then, it is easy to see that

$$\ln(n!)=\sum_{k=1}^n\ln(k)$$

And that is the right Riemann sum to the following integral:

$$\sum_{k=1}^n\ln(k)\ge\int_1^n\ln(x)\ dx=n\ln n-n+1$$

So we have proven the left side. Then notice that we have the following trapezoidal sum:

$$\frac{\ln(n)+2\ln((n-1)!)}2=\frac{\ln(n!)+\ln((n-1)!)}2\\=\sum_{k=1}^n\frac{\ln(k+1)+\ln(k)}2\\\le\int_1^n\ln(x)\ dx=n\ln(n)-n+1\\\frac{\ln(n)+2\ln((n-1)!)}2\le n\ln(n)-n+1\\\implies\ln((n-1)!)\le\left(n-\frac12\right)\ln(n)-n+1\\\implies\ln(n!)=\ln(n)+\ln((n-1)!)\le\left(n+\frac12\right)\ln(n)-n+1$$

Thus, when $n\ge1$,

$$\ln(n!)\le\left(n+\frac12\right)\ln(n)-n+1\le(n+1)\ln(n)-n+1$$

and we have everything we wanted.

$\endgroup$

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.