Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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)$ –  mt_ Jun 12 '12 at 10:14
    
@mt_ Thanks, I'll try. –  Frank Science Jun 12 '12 at 11:14
    
@mt_ You're quite right. Please post your complete answer and I'll set yours. –  Frank Science Jun 13 '12 at 13:31
    
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). –  mt_ Jun 13 '12 at 14:37
    
@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. –  Frank Science Jun 13 '12 at 14:45
show 1 more comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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