Limit of $\frac{\log(n!)}{n\log(n)}$ as $n\to\infty$.

Question

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?

Answer 1

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!

Answer 2

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.

Answer 3

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

Answer 4

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$

Answer 5

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.

Answer 6

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}

Answer 7

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

Answer 8

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

Answer 9

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

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

Answer 10

The upper bound is easy, as $x_n$ is bounded above by $\frac{\ln(x^x)}{x \ln x} = 1$.

Another form of Stirling's approximation gives the lower bound: $n! > \sqrt{2\pi n} (n/e)^n$, thus:

$$\lim_{n \to \infty} a_n > \lim_{n \to \infty} \frac{\frac{1}{2} \ln(2\pi n) + n \ln(n/e)}{n \ln n}= \lim_{n \to \infty}\frac{\frac{1}{2}\ln(2\pi)+\frac{1}{2}\ln n+ n \ln n - n \ln e}{n \ln n} =\boxed{1}.$$

Therefore, by the squeeze theorem we are done.

Answer 11

Using stirling's approximation $x! \sim \sqrt{2x\pi}(\frac{x}{e})^x$ thus $ ln(x!) \sim x(lnx-1)+\frac{ln(2x\pi)}{2}$ dividing by xln(x) we have $\frac{ln(x!)}{xlnx} \sim 1 -\frac{1}{lnx}+\frac{ln(2x\pi)}{2xlnx}$ all the terms except one tend to 0 as x tends to infinity and so $\frac{ln(x!)}{xlnx} \sim 1$