# Next term in $(1+a/n)^n \rightarrow \exp (n)$

Working on the generalized birthday problem, where you draw with replacement from $\{1,2,3, \ldots,d\}$ and look for the number of draws $n$ for which you have greater than $1/2$ chance of a match I said

$\frac{d!}{d^d(d-n)!} \lt \frac{1}{2}$

Using Stirling's approximation

$\frac{d^d \exp (d-n)} {\exp(d) d^n (d-n)^{(d-n)}} \lt \frac{1}{2}$
$\frac{1}{\exp(n)}(1+\frac{n}{d-n})^{(d-n)}\lt \frac{1}{2}$

Taking logs and using the Taylor expansion

$(d-n) \ln(1+\frac{n}{d-n})-n \lt -\ln (2)$
$(d-n) (\frac{n}{d-n}-\frac{n^2}{2(d-n)^2})\lt -\ln(2)$
$n^2>2 \ln(2) (d-n)$

Ignoring the n in comparison with d in the last term, because if we wanted it we should keep the next term in the expansion of ln, we get

$n>\sqrt{2 \ln (2) d}$ which agrees with the published result

This is fine, but like much math writing it obscures the difficulties of finding the solution. Before taking logs I wanted to say $(1+\frac{n}{d-n})^{(d-n)} \rightarrow \exp(n)$ but that left me with the unhelpful $1 \lt \frac{1}{2}$. Seeing what happened after taking logs, I need the next term in the expansion as the first one cancels. I know how to expand a Taylor series as far as I want, but I don't know what the next term in this one is.

-

$$\left(1+\frac{x}{n}\right)^{n}=e^x\left(1-\frac{x^2}{2n}+\frac{x^3(8+3x)}{24n^2}+\cdots\right).$$

-
Thanks. Using the first two terms gets me close, but doesn't turn the 1/2 to ln(2). –  Ross Millikan Nov 3 '10 at 13:43
The note you reference is cool. Thanks again. –  Ross Millikan Nov 3 '10 at 14:06
You're welcome. –  Andrey Rekalo Nov 3 '10 at 14:08
$$\rm\quad \bigg(1+\frac{a}n\bigg)^{\:n}\ =\ e^{n\log(1+a/n)}\ =\ e^a\ e^{n\log(1+a/n)-a}\$$
$$\rm n\:\log \bigg(1+\frac{a}n\bigg)-a\ =\ \frac{a^2}{2\:n} + \frac{a^3}{3\:n^2} +\: \cdots$$
$$\rm e^{n\log(1+a/n)-a}\ =\ 1 - \frac{a^2}{2\:n} + \frac{3a^4 + 8a^3}{24\: n^2} +\: \cdots$$