Given: 

 n, the number of days in a year, e.g.,  n= 365;

 k, the number of partygoers needed for the probability of two identical birthdays to exceed  1 - p, e.g.,  k= 23  for  p= .5;

 b, the number of different pairings of  k people, e.g., b= 253  for  k= 23;

 c, the number of partygoers needed for the probability of one of them having  your birthday to exceed  1 - p, e.g.,  c= 253  for  n= 365  and  p= .5;

and these well-known approximations:

 [A]       if a<< n

 [B]    if i<< j

we will show that:

 Substitute into [A]  yielding:

[C] 

 Multiply both sides by n

[D] 

 Raise both sides to the power k

[E] 

 Simplify the double exponent

[F] 

 Substitute b for 

[G] 

 On the left side, combine the powers of n

[H] 

[I] 

[J] 

 Substitute j = n- 2 , i = k- 2  into  [B] 

[K] 

[L] 

 The right sides of [J] and [L] are equal; pair the left sides

[M]

 Multiply both sides by n-1

[N] 

 Multiply both sides by n

[O] 

[P] 

 Divide both sides by 

[Q] 

[R] 

 Substitute p for 
[S] 

[T] 

 Substitute c for 

[U]

 QED.

I have not bounded the error analytically, but empirically, I have shown the error in:

to be within 1.0 when n> 4 and p> .04.

Home | The Birthday Problem | A Generalization | The Proof