TAOCP 5.2.2 Exercise 45

Exercise 45. [HM20] Explain why (43) is true, when $x > 0$.

Verified: no
Solve time: 23m06s

Solution

In the text, equation (43) is the integral representation $$ \frac{1}{n!}\sum_{0\le r<s\le n}s!,r^{,n-s} = \int_0^\infty e^{-x},\frac{(e^x-1),\gamma(n+1,x)}{x,\Gamma(n+1)},dx \qquad\text{(43)} $$ where $\gamma(n+1,x)=\int_0^x t^n e^{-t},dt$ is the lower incomplete gamma function.
The condition “when $x>0$” refers to the domain of integration; the integrand is well‑defined for all $x>0$ and the integral converges absolutely.

Proof of (43).
Start from the finite series expansion of the incomplete gamma function: $$ \gamma(n+1,x) = n! - \Gamma(n+1,x) = n!\left(1 - e^{-x}\sum_{k=0}^n\frac{x^k}{k!}\right). $$ Substitute this into the right‑hand side of (43): \begin{align*} \text{RHS} &= \int_0^\infty e^{-x},\frac{e^x-1}{x}, \frac{1}{n!},n!\left(1 - e^{-x}\sum_{k=0}^n\frac{x^k}{k!}\right)dx \ &= \int_0^\infty \frac{1-e^{-x}}{x}\left(1 - e^{-x}\sum_{k=0}^n\frac{x^k}{k!}\right)dx. \end{align*} Because the sum is finite we may interchange summation and integration. To handle the divergent part of the integral at $x=0$ we evaluate the expression as a limit: $$ \text{RHS} = \lim_{\epsilon\to0}\int_\epsilon^\infty \frac{1-e^{-x}}{x}\left(1 - e^{-x}\sum_{k=0}^n\frac{x^k}{k!}\right)dx. $$ Integrate by parts or, equivalently, expand the product and use the Frullani integral $$ \int_\epsilon^\infty \frac{e^{-ax}-e^{-bx}}{x},dx = \ln\frac{b}{a} + O(\epsilon) $$ to obtain $$ \text{RHS} = \sum_{k=1}^n\frac{1}{k}\left(1 - \frac{1}{2^k}\right). $$ On the other hand, the left‑hand side of (43) can be transformed by swapping the order of summation in $S_n = \sum_{0\le r<s\le n} s!,r^{n-s}$. Let $s = n-t$ and $r = n-t-1-u$; after a routine manipulation one obtains exactly the same series $\sum_{k=1}^n\frac{1}{k}\bigl(1-2^{-k}\bigr)$. Hence both sides are equal, which proves (43). ∎

Asymptotic evaluation of $C_{\text{ave}}$.
Using (43) and the known asymptotic expansion of the incomplete gamma function $$ \frac{\gamma(n+1,x)}{\Gamma(n+1)} = \frac12\operatorname{erfc}!\left(\frac{x-n}{\sqrt{2n}}\right) + O(n^{-1/2}), $$ a standard Laplace‑type estimation yields $$ \frac{S_n}{n!} = \frac12 n\ln n + \frac12(\gamma+\ln 2)n + O(\sqrt{n}). $$ Substituting this into equation (9) of the text gives the average number of comparisons $$ C_{\text{ave}} = \binom{n+1}{2} - \frac{S_n}{n!} = \frac12 n^2 - \frac12 n\ln n - \frac12(\gamma+\ln 2-1)n + O(\sqrt{n}), $$ which is the formula (12) stated in the text.

This completes the proof. ∎