Obtain asymptotically tight bounds on \(\lg(n!)\) without using Stirling’s approximation. Instead, evaluate the summation \(\sum_{k=1}^n \lg k\) using techniques from Section A.2.

\(\sum_{k=1}^n \lg k\) satisfies the requirement of (A.11) in that it is monotonically increasing and so we can approximate the sum using integrals:

\[\begin{split} \int_0^n \lg(x)dx &\le \sum\limits^{n}_{k=1} \lg(k) \\ &\le \int_1^{n+1} \lg(x) dx \end{split}\]

Evaluating this integral produces:

\[\frac{n \ln (n) - n}{\ln 2} \le \sum\limits^{n}_{k=1} \lg(k) \le \frac{(n+1) \ln (n+1) - n}{\ln 2}\]

For the lower bound, \(\frac{n \ln n - n}{\ln 2} = \frac{n \ln n \left(1 - \frac{1}{\ln n}\right)}{\ln 2}\) with \(\left(1 - \frac{1} {\ln n}\right)\) trending towards \(1\) for large \(n\). So this term is \(\approx \frac{n \ln n}{\ln 2} = n \lg n\), giving us a lower bound of \(\Omega(n\lg n)\).

For the upper bound, \(\frac{(n+1) \ln (n+1) - n}{\ln 2}\), we focus first on the numerator: \((n+1) \ln (n+1) - n\). Using the identity \(\ln (n+1) = \ln n + \ln \left( 1 + \frac{1}{n} \right)\) we obtain:

\[(n+1) \ln (n+1) = (n + 1) \left( \ln n + \ln \left( 1 + \frac{1}{n} \right) \right) = (n + 1) \ln n + (n + 1) \ln \left(1 + \frac{1}{n} \right)\]

Next, consider the standard bound \(\ln (1+x) \le x\) for all \(x > -1\). With \(x = \frac{1}{n}\), we have \(\ln \left( 1 + \frac{1}{n} \right) \le \frac{1}{n}\). So \((n+1) \ln \left( 1 + \frac{1}{n} \right) \le (n+1) \cdot \frac{1}{n} = 1 + \frac{1}{n}\). Therefore, \((n+1) \ln (n+1) \le (n + 1) \ln n + 1 \frac{1}{n}\). If we now subtract \(n\), we have:

\[(n+1) \ln (n+1) - n \le (n+1) \ln n + 1 + \frac{1}{n} - n\]

The \(n+1 \ln (n+1)\) portion of this is the main term that grows much faster than the remainder term of \(1 + \frac{1}{n} - n\) and so we may safely discard all but the main term. Furthermore, expanding the main term into \(n \ln n + \ln n\) allows us to discard more slow-growing terms once again and proceed with only \(n \ln n\). Recall that we were working with just the numerator to start, so let’s re-introduce the denominator:

\[\frac{n\ln(n)}{\ln 2} = n \lg n\]

Giving us a an upper bound of \(O (n \lg n)\).

In conclusion, we have a lower bound of \(\Omega(n \lg n)\) and an upper bound of \(O(n \lg n)\) giving us a tight \(\Theta (n \lg n)\) bound.