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
    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)$2012-06-12
  • 0
    @mt_ Thanks, I'll try.2012-06-12
  • 0
    @mt_ You're quite right. Please post your complete answer and I'll set yours.2012-06-13
  • 0
    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).2012-06-13
  • 0
    @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.2012-06-13
  • 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.