4
$\begingroup$

I am solving an exercise and can't advance in the following induction:

$$n\log n - n + 1 \leq \log n!.$$

If necessary, i put the complete question.

  • Update

Calculate $$\lim_{n\to \infty}\frac{n!e^{n}}{n^{n}}$$ following the steps bellow:

A. Show that: $$\int\limits_{1}^{n}\log x\,\mathrm{d}x = n\log n - n + 1 = A_{n}.$$ B. If $B_{n}$ is the right Riemman sum of the function $\log x$ relative to the partition $\lbrace 1, ..., n\rbrace$ of the interval $[1, n]$, show that: $$A_{n} \leq B_{n} = \sum_{k = 2}^{n}\log k = \log n!.$$

C.

D.

E.

F.

The steps C, D, E and F are not relevant for my doubt.

$\endgroup$
  • $\begingroup$ Adding more detail would be a good idea; people are more likely to help you here when you present the context of the problem and the attempts you've made or thoughts you've had to solve it. $\endgroup$ – Robert Howard Feb 13 '18 at 5:23
  • $\begingroup$ @RobertHoward , Sure! $\endgroup$ – Corrêa Feb 13 '18 at 5:27
  • 1
    $\begingroup$ The log function is increasing, so the right Riemann sum is greater than or equal to the integral. So the inequality follows from part (A). No need for induction. $\endgroup$ – fredgoodman Feb 13 '18 at 5:46
  • $\begingroup$ Yes, of course! Thanks for de help! @fredgoodman $\endgroup$ – Corrêa Feb 13 '18 at 5:57
  • $\begingroup$ Using just the integral from $n$ to $n+1$, you get an inequality equivalent to $(1 + 1/n)^n \le e$. $\endgroup$ – fredgoodman Feb 13 '18 at 6:02
2
$\begingroup$

Base case $n=1 \implies 1\log1-1+1 \leq \log (1!) \implies 0 \leq 0$

Base case $n=2 \implies 2\log2-2+1 \leq \log (2!) \implies \log 2 \leq 1$

We assume this proposition to be true $$ \text {(P) }n\log n - n + 1 \leq \log n!$$ We try to prove that

$$(n+1)\log( n+1) - (n+1)+1 \leq \log ((n+1)!)$$ $$(n+1)\log( n+1) - n \leq \log(n+1)+\log (n!)$$ Substract $\log (n+1)$

$$n\log( n+1) - n \leq \log (n)!$$ $$n(\log n( 1+ \frac 1 n)) - n \leq \log (n!)$$ $$n\log(n)+\log( 1+ \frac 1 n)^n - n \leq \log (n!)$$

Note that $\log( 1+ \frac 1 n)^n\leq \log e=1$ And $$n\log(n)+\log( 1+ \frac 1 n)^n - n \leq n\log(n)+1 - n \leq \log (n!)$$ So P is true for $n=1,2$ and we proved by induction that if P is true for n then it's also true for $n+1$ So we can conclude that P is true for any $n \in \mathbb{N} (n\ne 0)$

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Starting from the fundamental $(1+\frac{1}{n})^n \leq e$ for all $n>0$, we get the inequality $$\tag{*} en^n \geq (n+1)^n$$

I'd prefer to work with exponentials over logs, so note that your inequality is equivalent to $$\tag{H} n! \geq e\left(\frac{n}{e}\right)^n $$

For the inductive step, we assume $n! \geq e\left(\frac{n}{e}\right)^n $ and want to show $(n+1)! \geq e\left(\frac{n+1}{e}\right)^{n+1}$.

This follows as below. The first inequality is the inductive hypothesis (H) and the second inequality is our knowledge of a lower bound for $e$ (*)

$$(n+1)! = (n+1) n! \geq (n+1) e\left(\frac{n}{e}\right)^n = \frac{n+1}{e^n} en^n \geq \frac{n+1}{e^n}(n+1)^n = e \left(\frac{n+1}{e} \right)^{n+1}$$

Don't forget to establish the base case!

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Hint: $$ \begin{align} &((n+1)\log(n+1)-(n+1)+1)-(n\log(n)-n+1)\\ &=\log(n+1)+n\log\left(1+\frac1n\right)-1\\ \end{align} $$ and $$ n\log\left(1+\frac1n\right)=\int_n^{n+1}\frac nx\,\mathrm{d}x\lt1 $$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Let $F(n)=-n+1+n\ln n.$

Let $G(n)=\ln (n!).$

If $F(n+1)-F(n)\leq G(n+1)-G(n)$ then $(\;F(n)\leq G(n)\implies F(n+1)\leq G(n+1)\;).$

We have $F(n+1)-F(n)=-1-n \ln n +(n+1)\ln (n+1).$

We have $G(n+1)-G(n)=\ln (n+1).$ $$ \text {Hence }\quad F(n+1)-F(n)\leq G(n+1)-G(n)\iff $$ $$\iff -1-n \ln n +(n+1)\ln (n+1)\leq \ln (n+1)\iff$$ $$\iff -n \ln n+(n+1)\ln (n+1)\leq 1\iff$$ $$\iff n\ln (1+\frac {1}{n})\leq 1.\quad (\bullet)$$

For $x>0$ we have $\ln (1+x)=\int_1^{1+x}\frac {1}{y}dy$ $<\int_1^{1+x}1dy=x.$ Therefore for $n>0$ we have $n\ln ((1+\frac {1}{n})<n \cdot \frac {1}{n}=1.$

So $(\bullet)$ does hold for all $n>0.$

| cite | improve this answer | |
$\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.