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!

  • $\begingroup$ Maybe it helps to use $k\log m = k(n-1/2)/m$ since you will also have $nk/m$ appearing from $n\log(m+k)$ $\endgroup$ – Matthew Towers Jun 12 '12 at 10:14
  • $\begingroup$ @mt_ Thanks, I'll try. $\endgroup$ – Yai0Phah Jun 12 '12 at 11:14
  • $\begingroup$ @mt_ You're quite right. Please post your complete answer and I'll set yours. $\endgroup$ – Yai0Phah Jun 13 '12 at 13:31
  • $\begingroup$ I don't have a complete answer! I just thought that looked like the right thing to do. I'd be interested to see your solution if you feel like writing it up though (you can accept your own answer). $\endgroup$ – Matthew Towers Jun 13 '12 at 14:37
  • $\begingroup$ @mt_ I've just been working on it almost 3 hours. If I accepted my answer, the others would think that I'm just tricking. $\endgroup$ – Yai0Phah Jun 13 '12 at 14:45

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.