6
$\begingroup$

Concrete Mathematics EXERCISE 9.46

Show that the Bell number $\varpi_n=e^{-1}\sum_{k\ge0}k^n/k!$ of exercise 7.15 is asymptotically equal to \[ m(n)^ne^{m(n)-n-1/2}/\sqrt{\ln n} \] where $m(n)\ln m(n) = n-\frac12$, and estimate the relative error in this approximation.

Part of the answer is that (According to the errata, I've edited the answer)

For convenience we write just $m$ instead of $m(n)$. By Stirling's approximation, the maximum value of $k^n/k!$ occurs when $k\approx m\approx n/\ln n$, so we replace $k$ by $m+k$ and find that \begin{align*} \ln\frac{(m+k)^n}{(m+k)!}=&n\ln m-m\ln m+m-\frac{\ln 2\pi m}2\\ &-\frac{(m+n)k^2}{2m^2}+O(k^3m^{-2}\log n)+O(1/m)\tag1 \end{align*} Actually we want to replace $k$ by $\lfloor m\rfloor+k$; this adds a further $O(km^{-1}\log n)$. The tail-exchange method with $|k|\le m^{1/2+\epsilon}$ now allows us to sum on $k$, ...

How can we derive equation (1) (especially when $|k|\le m^{1/2+\epsilon}$)? I try to expand $\ln(m+k)!$ using Stirling's approximation. It gets \[ \ln(m+k)!=(m+k)\ln(m+k)-(m+k)+\frac12\ln(m+k)+\sigma+O(1/m) \] where $e^\sigma=\sqrt{2\pi}$. However, the term $k\ln m$ in \[ (m+k)\ln(m+k)=(m+k)(\ln m+\ln(1+k/m))=(m+k)\left(\ln m-k/m+O(k/m)^2\right) \] never vanishes, and it's $\Omega(1)=\omega\left(k^3m^{-2}\log n\right)$ when $k$ is small.

Any help? Thanks!

  • 0
    Well it's up to you. I don't think anyone would mind, and I'd like to see it - but you decide.2012-06-13

1 Answers 1

4

You're doing the right things, as far as I can tell. Maybe you're not using $n = m \log m + 1/2$ or $n/\log n = m + o(m)$ in the right place? (The latter asymptotic comes from $\log n = \log m + \log(\log m + 1/(2m))$ and doing the division of $n$ by $\log n$. The dominant term is $m$.) At any rate, here's the derivation I get.


We need Stirling's approximation $\log (m+k)! = (m+k) \log(m+k) - (m+k) + \frac{1}{2}\log(m+k) + \frac{1}{2} \log (2\pi) + O\left(\frac{1}{m}\right)$ and $\log(m+k) = \log m + \log\left(1 + \frac{k}{m}\right) = \log m + \frac{k}{m} - \frac{k^2}{2m^2} + O\left(\frac{k^3}{m^3}\right).$ We have $\log \frac{(m+k)^n}{(m+k)!} = n \log (m+k) - \log(m+k)!.$ Let's take these two terms separately. \begin{align*} n \log (m+k) &= n \log m + \frac{nk}{m} - \frac{nk^2}{2m^2} + O\left(\frac{nk^3}{m^3}\right) \\ &= n \log m + k \log m + \frac{k}{2m} - \frac{nk^2}{2m^2} + O\left(\frac{k^3 \log n}{m^2}\right). \tag{1} \end{align*} And \begin{align} - \log(m+k)! = &-(m+k)\left(\log m + \frac{k}{m} - \frac{k^2}{2m^2} + O\left(\frac{k^3}{m^3}\right)\right) \\ & + (m+k) - \frac{1}{2}\left(\log m + \frac{k}{m} + O\left(\frac{k^2}{m^2}\right)\right) - \frac{1}{2} \log (2\pi) + O\left(\frac{1}{m}\right) \\ =&- (m+k)\log m -k - \frac{k^2}{m} + \frac{k^2}{2m} + m+k - \frac{\log m}{2} - \frac{k}{2m} \\ &- \frac{1}{2} \log (2\pi) + O\left(\frac{k^3}{m^2}\right) + O\left(\frac{1}{m}\right)\\ =& - (m+k) \log m + m - \frac{\log(2 \pi m)}{2} - \frac{k^2}{2m} - \frac{k}{2m} + O\left(\frac{k^3}{m^2}\right) + O\left(\frac{1}{m}\right). \tag{2} \end{align}

Adding Eqs. (1) and (2), we get \begin{align} &\log \frac{(m+k)^n}{(m+k)!} \\ &= n \log m - m \log m + m - \frac{\log(2 \pi m)}{2} - \frac{(m+n)k^2}{2m^2} + O\left(\frac{k^3 \log n}{m^2}\right) + O\left(\frac{1}{m}\right), \end{align} which is the expression given by Concrete Mathematics.