14
$\begingroup$

I can't seem to find a good way to solve this.

I tried using L'Hopitals, but the derivative of $\log(n!)$ is really ugly. I know that the answer is 1, but I do not know why the answer is one.

Any simple way to go about this?

$\endgroup$
  • $\begingroup$ I input my question wrong. I meant to have the denominator as nlog(n). $\endgroup$ – Bobby Brown Apr 30 '13 at 7:39
  • $\begingroup$ I have updated my answer and it should answer your question now. $\endgroup$ – user17762 Apr 30 '13 at 7:40
15
$\begingroup$

The numerator is

$$ \log(n!) = \log 1 + \log 2 + \log 3 + \cdots + \log n $$

The terms have an obvious upper bound: $\log n$. Thus,

$$ \log(n!) \leq \log n + \log n + \log n + \cdots + \log n = n \log n $$

Thus, $\log(n!) / (n \log n) \leq 1$, always.

Half of the terms have an obvious lower bound: $\log (n/2)$.

$$ \log(n!) \geq (n/2) \log(n/2) $$

Thus,

$$\lim \frac{\log n!}{n \log n} \geq \lim \frac{(n/2) \log(n/2)}{n \log n} = \frac{1}{2} $$

But we also know that three quarters of the terms have the lower bound $\log(n/4)$, so

$$\lim \frac{\log n!}{n \log n} \geq \lim \frac{(3n/4) \log(n/ 4)}{n \log n} = \frac{3}{4} $$

And so forth: we can show that the limit is bigger than every number less than 1.

And so we apply the ancient principle of exhaustion! If the limit is bigger than every number less than 1, then the limit can't be smaller than 1. But we know the limit can't be bigger than 1 either. Therefore, it must be 1!

$\endgroup$
  • 3
    $\begingroup$ This assumes the limit exists, but can be made rigorous by talking about $\limsup$ and $\liminf$. $\endgroup$ – Aryabhata May 1 '13 at 2:11
  • $\begingroup$ Great answer, very intuitive while still rigorous (in my eyes). $\endgroup$ – jeremy radcliff Feb 5 '17 at 7:02
9
$\begingroup$

First, use that $n^n > n!$ for all $n > 1$, thus $n \log(n) > \log(n!)$ and so $1 > \dfrac{\log(n!)}{n \log(n)}$. Now, from a basic theorem of Stirling's approximation, we have $n \log(n) - n < \log(n!)$, so we have $1 - \dfrac{1}{\log(n)} < \dfrac{\log(n!)}{n \log(n)}$. Combining these, we have $1 - \dfrac{1}{\log(n)} < \dfrac{\log(n!)}{n \log(n)} < 1$. It is easy to see that $\lim_{n \rightarrow \infty} 1 - \dfrac{1}{\log(n)} = 1$ and trivial that $\lim_{n \rightarrow \infty}1 = 1$, so by the squeeze theorem, $\lim_{n \rightarrow \infty} \dfrac{\log(n!)}{n \log(n)} = 1$.

To prove that $n^n > n!$, it suffices to compare the terms of their product expansions (i.e. $n^n = n \cdot n \cdot n \cdots n$ ($n$ times) and $n! = 1 \cdot 2 \cdot 3 \cdots n$.).

$\endgroup$
  • $\begingroup$ $(+1)$ for the Sandwich Theorem.:) $\endgroup$ – Inceptio Apr 30 '13 at 19:36
  • 2
    $\begingroup$ "From a basic theorem of Stirling's approximation...". I don't think Stirling's approximation is basic, given OP's background. $\endgroup$ – user17762 May 1 '13 at 2:08
  • 2
    $\begingroup$ If you are using Stirling's Approximation, just use it and make your answer a one liner!: $\log n! = n\log n - n + O(\log n)$. Why talk about all the inequalities? $\endgroup$ – Aryabhata May 1 '13 at 2:12
  • $\begingroup$ @user17762: It depends; I can easily imagine an analysis of algorithms course (which I'm guessing the OP is in) introducing it, because of its great utility in dealing with factorials and the fact CS students are very likely never to encounter it in their math classes. $\endgroup$ – Excluded and Offended May 1 '13 at 4:03
8
$\begingroup$

From the Taylor series of $e^x$, we have $$e^x = 1 + \sum_{k=1}^{\infty} \dfrac{x^n}{n!}$$ From this we get that, $e^x \geq \dfrac{x^n}{n!}$, for $x \in \mathbb{R}^+$ and $n \in \mathbb{Z}^+$.

Setting $x=n$ we get that $$e^n \geq \dfrac{n^n}{n!} \implies n! \geq \left(\dfrac{n}e \right)^n$$ Hence, we have $$\log(n!) \geq n \log n - n$$ Also, note that $$\log(n!) = \sum_{k=1}^n \log(k) \leq \sum_{k=1}^n \log(n) = n \log(n)$$ We hence have $$n \log(n) - n \leq \log(n!) \leq n \log(n)$$ Now you should be able to finish it off from here.

$\endgroup$
  • $\begingroup$ Thanks for the explanation, but this is for a computer science course, and I have not even gotten to Taylor Series in calculus yet. I doubt the solution must be this hard; I must be overlooking an easier way to do this problem, and, again, thanks for the help. $\endgroup$ – Bobby Brown Apr 30 '13 at 7:47
  • 1
    $\begingroup$ @BobbyBrown If you are not familiar with the expansion of $\exp(x)$, you should probably not sit through the computer science course. $\endgroup$ – user17762 Apr 30 '13 at 8:06
  • 3
    $\begingroup$ @user17762: That surely isn't motivating him to learn about $e^x$ or $\exp(x)$ $\endgroup$ – Inceptio Apr 30 '13 at 8:09
4
$\begingroup$

By Stolz Cezaro

$$ \lim_n \frac{\log(n!)}{n\log(n)} = \lim_n \frac{\log(n+1)}{(n+1)\log(n+1)-n\log(n)} = \lim_n \frac{\log(n+1)}{\log(n+1)+n\log(\frac{n+1}{n})}\\= \lim_n \frac{\log(n+1)}{\log(n+1)+\log(\frac{n+1}{n})^n}= \lim_n \frac{1}{1+\frac{\log(\frac{n+1}{n})^n}{\log(n+1)}}=1 $$ the last equality following from $\lim_n \log\left(\frac{n+1}{n}\right)^n=e$

$\endgroup$
  • $\begingroup$ This clearly does not change results, however: When using Stolz Cesaro, shouldn't you get in the first step $\log(n+1)=\log((n+1)!)-\log(n!)$ rather than $\log(n)$. $\endgroup$ – Martin Sleziak Jun 18 at 4:46
  • $\begingroup$ @MartinSleziak Ty, fixed. $\endgroup$ – N. S. Jun 18 at 5:33
  • $\begingroup$ Sorry for the nitpicking, but couldn't you then finish the computation simply by $$\lim_n \frac{\log(n+1)}{\log(n+1)+\log(\frac{n+1}{n})^n} = \lim_n \frac{1}{1+\frac{\log(\frac{n+1}{n})^n}{\log(n+1)}}.$$ The way it is written in the current revision seems (to me) more complicated than needed, unless I missed something. $\endgroup$ – Martin Sleziak Jun 18 at 5:40
3
$\begingroup$

There are $n!$ ways of showing that $\frac{\ln(n!)}{n \ln n} \to 1$; here is one of them.

We start with $\ln(n!) = \sum_{k=1}^n \ln k$ and estimate $\ln k$.

$(x+1)\ln(x+1)-x \ln x = x(\ln(x+1)-\ln(x))+\ln(x+1) =x\ln(1+1/x)+\ln(x+1) $ so $ (x+1)\ln(x+1)-x \ln x -\ln(x+1)=x\ln(1+1/x)$.

Using $0 < \ln(1+z) < z$ for $0 < z < 1$, $0 < (x+1)\ln(x+1)-x \ln x -\ln(x+1) < 1$. This is just an approximate form of $\int \ln x\,dx = x \ln x - x$ or $\ln x = (x \ln x)' - 1$.

Summing for $x$ from 1 to $n-1$, $0 < \sum_{x=1}^{n-1} \big((x+1)\ln(x+1)-x \ln x -\ln(x+1)\big) < n-1 $ or, since the left part of the sum is telescoping and the right part gives $\ln(n!)$, $0 < n \ln n -\ln(n!) < n-1 < n$.

Dividing by $n \ln n$, $0 < 1-\frac{\ln(n!)}{n \ln n} < \frac{1}{\ln n}$, and this gives it to us.

$\endgroup$
2
$\begingroup$

Based on the basic properties of logarithms and a simple integral approximation, we can rewrite $\log(n!)$ as follows:

\begin{eqnarray} \log(n!) = \log(1 \times 2 \times 3 \times \dots \times n) = \log(1) + \log(2) + \log(3) + \cdots+ \log(n) = \end{eqnarray} \begin{eqnarray} \sum_{i=1}^{n} \log(i) \approx \int_1^n \log(x)\,\mathrm{d}x = [x\log(x) -x]_{1}^{n} = n\log(n)-n+1 \approx n\log(n) - n \end{eqnarray}

Thus,

\begin{eqnarray} \lim_{n \to \infty} \frac{\log(n!)}{n\log(n)} \approx \frac{n\log(n) - n}{n\log(n)} = 1 - \lim_{n \to \infty} \frac{1}{\log(n)} =1. \end{eqnarray}

$\endgroup$
  • 1
    $\begingroup$ @IshanBanerjee It's not equal, but since $\log$ is increasing we have $$\int_1^{n} \log x \,\mathrm{d}x \leq \sum_{i=2}^n \log i \leq \int_2^{n+1} \log x \,\mathrm{d}x$$ $\endgroup$ – Petr Pudlák Apr 30 '13 at 21:00
2
$\begingroup$

Let us show your limit is $1$ in an elementary way without calculus. WLOG we replace $n$ by $2^n$.

$$\sum_{1\le k \le 2^n} \ln k >\sum_{1\le k\le n-1} 2^{k}\ln 2^{k}$$

Now we shall prove $$\frac{\sum_{1\le k\le n-1} k2^k}{n 2^n} \to 1.$$ Replace $k$ by $n-k$, $$\frac{\sum_{1\le k\le n-1} (n-k)2^{-k}}{n}\to 1,$$ or $$\sum_{1\le k\le n-1} \frac{k}{n}2^{-k}\to 0, $$ the rest is yours (using $k2^{-k}\to 0$).

$\endgroup$
1
$\begingroup$

A completely elementary way:

By the mean value theorem, we have that

$$\frac{1}{j} \le \log j - \log (j-1) \le \frac{1}{j-1}$$

Setting $j=2$ to $k$ and adding up yields

$$H_{k} - 1 \le \log k \le H_{k-1} \quad \quad (1)$$

where $H_{k}$ is the $k^{\text{th}}$ harmonic number.

Note that this shows that $\frac{H_n}{\log n} \to 1$ as $n \to \infty$.

We can easily show that (induction or otherwise)

$$ S_n = \sum_{k=1}^{n} H_k = (n+1)H_n - n \quad \quad (2)$$

Since $\frac{H_n}{\log n} \to 1$, we have that $\frac{S_n}{n \log n} \to 1$.

Setting $k=2$ to $n$ in $(1)$, adding up and using $(2)$ gives us

$$ S_n - n \le \log n! \le S_{n-1}$$

Now divide by $n \log n$, and use the result that $\frac{S_n}{n\log n} \to 1$.

$\endgroup$
1
$\begingroup$

don't need Stirling. For a function such as logarithm with $f(x) > 0$ and $f'(x) > 0,$ we get $$ \int_{a-1}^b \; f(x) dx < \sum_{k=a}^b \; f(k) < \int_{a}^{b+1} \; f(x) dx $$

Here $f$ is log base e, take $a=2$ and $b=n$ $$ \int_{1}^n \; \log x \; dx < \sum_{k=2}^n \; \log k < \int_{2}^{n+1} \; \log x \; dx $$

An antiderivative of $\log x$ is $x \log x - x.$

$$ n \log n - n + 1 < \log n! < (n+1) \log (n+1) - n - 1 - 2 \log 2 + 2 $$

enter image description here

..................

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