TAOCP 1.2.11.2 Exercise 7

Let P_n = 1^1 2^2 3^3 \cdots n^n = \prod_{k=1}^n k^k.

taocpmathematicsalgorithmsvolume-1hm-hard

Section 1.2.11.2: Euler's Summation Formula

Exercise 7. [HM32] What is the approximate value of $1^1 2^2 3^3 \cdots n^n$?

Verified: yes
Solve time: 44s

Setup

Let

$$ P_n = 1^1 2^2 3^3 \cdots n^n = \prod_{k=1}^n k^k. $$

We are asked to find an approximate value of $P_n$ for large $n$. Following the argument in Section 1.2.11.2, we will take logarithms to convert the product into a sum, then apply Euler's summation formula to estimate that sum. Define

$$ S(n) = \ln P_n = \sum_{k=1}^n k \ln k. $$

The task is then to find an asymptotic expression for $S(n)$ and exponentiate to obtain an approximation for $P_n$.

By Euler's summation formula (Section 1.2.11.2), if $f(x)$ is sufficiently smooth,

$$ \sum_{k=1}^n f(k) = \int_1^n f(x), dx + \frac{f(n)+f(1)}{2} + \sum_{j=1}^{m} \frac{B_{2j}}{(2j)!} \left(f^{(2j-1)}(n) - f^{(2j-1)}(1)\right) + R_m, \tag{1} $$

where $B_{2j}$ are Bernoulli numbers and $R_m$ is the remainder term. We will apply this to $f(x)=x\ln x$.

Solution

Let $f(x)=x\ln x$. Then

$$ f'(x) = \ln x + 1, \quad f''(x) = 1/x, \quad f^{(k)}(x) = (-1)^{k-2} (k-2)! / x^{k-1} \text{ for } k \ge 2. $$

First, compute the integral:

$$ \int_1^n x \ln x , dx = \frac{x^2}{2} \ln x - \frac{x^2}{4} \Big|_1^n = \frac{n^2}{2} \ln n - \frac{n^2}{4} - \left( \frac{1}{2} \ln 1 - \frac{1}{4} \right) = \frac{n^2}{2} \ln n - \frac{n^2}{4} + \frac{1}{4}. $$

Next, the endpoint correction:

$$ \frac{f(n)+f(1)}{2} = \frac{n\ln n + 0}{2} = \frac{n\ln n}{2}. $$

The first Bernoulli correction uses $B_2 = 1/6$ and $f'(x) = \ln x + 1$:

$$ \frac{B_2}{2!} (f'(n)-f'(1)) = \frac{1/6}{2} \big( (\ln n +1) - (0 +1) \big) = \frac{1}{12} \ln n. $$

Higher-order Bernoulli terms are $O(1/n)$ and can be included in a remainder term. Therefore, by Euler's summation formula,

$$ S(n) = \sum_{k=1}^n k \ln k = \frac{n^2}{2} \ln n - \frac{n^2}{4} + \frac{n \ln n}{2} + \frac{1}{12} \ln n + c + O\left(\frac{1}{n}\right), $$

where $c$ is a constant arising from $f(1)$ and higher-order Bernoulli terms. Collecting terms with powers of $n$ gives

$$ S(n) = \frac{n^2}{2} \ln n - \frac{n^2}{4} + \frac{n}{2} \ln n + \frac{1}{12} \ln n + O(1). $$

Exponentiating,

$$ P_n = e^{S(n)} \approx \exp\left( \frac{n^2}{2} \ln n - \frac{n^2}{4} + \frac{n}{2} \ln n + \frac{1}{12} \ln n \right) \cdot e^{O(1)}. $$

Combining logarithms:

$$ \frac{n^2}{2} \ln n + \frac{n}{2} \ln n = \frac{n(n+1)}{2} \ln n. $$

Hence

$$ P_n \approx A , n^{n(n+1)/2} e^{-n^2/4} , n^{1/12} = A , n^{n(n+1)/2 + 1/12} e^{-n^2/4}, $$

where $A = e^{O(1)}$ is a constant of order unity. This completes the derivation of the approximate value.

$$ \boxed{P_n \sim A , n^{n(n+1)/2 + 1/12} e^{-n^2/4}} $$

Verification

Check each component. The integral

$$ \int_1^n x\ln x , dx = \frac{n^2}{2} \ln n - \frac{n^2}{4} + \frac{1}{4} $$

matches direct integration by parts. The endpoint correction is $\frac{n\ln n}{2}$, consistent with $(f(n)+f(1))/2$. The first Bernoulli term using $B_2/2! (f'(n)-f'(1)) = (1/12) \ln n$ agrees with the formula. Higher-order terms contribute $O(1/n)$, which is absorbed in $A = e^{O(1)}$. Exponentiating produces the correct combination of powers and exponentials. This confirms the asymptotic formula.

Notes

The constant $A$ can, in principle, be computed explicitly using the full Euler-Maclaurin expansion and known values of $B_{2k}$, but for an asymptotic estimate the $O(1)$ term suffices. This method generalizes to products of the form $\prod_{k=1}^n k^{\alpha k + \beta}$ by replacing $f(x)$ with $(\alpha x + \beta) \ln x$.

∎