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.

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.

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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

This note might be helpful.

share|improve this answer
    
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 $$

share|improve this answer

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.