Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
Shouldn't that be "exp(a)" in the question? – EsperantoSpeaker1 Aug 20 '14 at 5:04
@EsperantoSpeaker1: You are correct. Thanks. – Ross Millikan Aug 21 '14 at 14:47
up vote 5 down vote accepted


This note might be helpful.

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

Your Answer


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.