The Birthday Problem

The Proof

We will show that the coincidence, suspected by the author to have no mathematical significance, was not a coincidence at all.

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, that is, b=(k(k-1)/2, 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;
[A]
if a<< n
[B]
if i<< j

we will show that:

is not a coincidence, but is true for all reasonable values of  n and  p.

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.