TAOCP 7.2.1.5 Exercise 50
We define $\xi(x)$ for $x>0$ as the unique positive solution of $\xi e^{\xi}=x$.
Section 7.2.1.5: Generating All Set Partitions
Exercise 50. ▶ [HM21] If $\xi(n)e^{\xi(n)}=n$ and $\xi(n)>0$, how does $\xi(n+k)$ relate to $\xi(n)$?
Verified: no
Solve time: 3m03s
Solution
We define $\xi(x)$ for $x>0$ as the unique positive solution of $\xi e^{\xi}=x$. Thus $\xi(n)>0$ satisfies
[
\xi(n),e^{\xi(n)} = n.
]
For a given integer $k\ge 0$ we wish to relate $\xi(n+k)$ to $\xi(n)$.
Let $\xi = \xi(n)$ and $\eta = \xi(n+k)$. By definition, [ \eta e^{\eta} = n+k = \xi e^{\xi} + k. \tag{1} ]
Exact implicit relation
Divide (1) by $e^{\eta}$ and take logarithms: [ \eta = \ln(\xi e^{\xi}+k) - \ln\eta. ] Since $\ln(\xi e^{\xi}+k) = \ln(\xi e^{\xi}) + \ln!\left(1+\frac{k}{\xi e^{\xi}}\right) = \xi + \ln\xi + \ln!\left(1+\frac{k}{n}\right)$, we obtain [ \eta = \xi + \ln\xi + \ln!\left(1+\frac{k}{n}\right) - \ln\eta. ] Rearranging and setting $\varepsilon = \eta - \xi = \xi(n+k)-\xi(n)$ yields the exact implicit equation [ \varepsilon = \ln!\left(1+\frac{k}{n}\right) - \ln!\left(1+\frac{\varepsilon}{\xi}\right). \tag{2} ] Equivalently, using $n = \xi e^{\xi}$, [ \varepsilon = \ln!\left(1+\frac{k e^{-\xi}}{\xi}\right) - \ln!\left(1+\frac{\varepsilon}{\xi}\right). \tag{2'} ]
Asymptotic expansion for large $n$
For large $n$, $\xi = \xi(n) \sim \ln n \to \infty$ and $k/n = k e^{-\xi}/\xi$ is small. We solve (2) by expanding both logarithms: [ \ln(1+k/n) = \frac{k}{n} - \frac{k^2}{2n^2} + \frac{k^3}{3n^3} - \cdots, \qquad \ln(1+\varepsilon/\xi) = \frac{\varepsilon}{\xi} - \frac{\varepsilon^2}{2\xi^2} + \frac{\varepsilon^3}{3\xi^3} - \cdots. ] Substituting into (2) gives [ \varepsilon + \frac{\varepsilon}{\xi} - \frac{\varepsilon^2}{2\xi^2} + \cdots = \frac{k}{n} - \frac{k^2}{2n^2} + \cdots. ]
Solving perturbatively, the first‑order term is [ \varepsilon_1 = \frac{k}{n(1+1/\xi)} = \frac{k,\xi}{n(\xi+1)} = \frac{k}{e^{\xi}(\xi+1)}. ] For the second‑order term we substitute $\varepsilon = \varepsilon_1 + \varepsilon_2 + \cdots$ into the quadratic terms: [ \varepsilon_2 = \frac{1}{1+1/\xi}\left( \frac{\varepsilon_1^2}{2\xi^2} - \frac{k^2}{2n^2} \right) = -\frac{k^2}{2n^2},\frac{2\xi+1}{(\xi+1)^3} + O!\left(\frac{k^3}{n^3}\right). ] Thus we have the asymptotic expansion [ \xi(n+k) = \xi(n) + \frac{k,\xi(n)}{n(\xi(n)+1)} - \frac{k^2}{2n^2},\frac{2\xi(n)+1}{(\xi(n)+1)^3} + O!\left(\frac{k^3}{n^3}\right). \tag{3} ]
This relation is the one used in the saddle‑point analysis of the Bell numbers.
\boxed{\xi(n+k) = \xi(n) + \frac{k,\xi(n)}{n(\xi(n)+1)} - \frac{k^2}{2n^2},\frac{2\xi(n)+1}{(\xi(n)+1)^3} + O!\left(\frac{k^3}{n^3}\right)}
For fixed $k$ and $n\to\infty$ the first‑order approximation $\xi(n+k) \approx \xi(n) + \frac{k}{e^{\xi(n)}(\xi(n)+1)}$ often suffices.
This completes the proof. ∎