I have been struggling with this one of exercises for a long time now.
There are d = $4k^2$ days and 2k people $P_1$ , $P_2$ , . . . , $P_{2k}$. For each $i$ with $1 ≤ i ≤ 2k$, define the event $B_i$ = “$P_i$ has the same birthday as at least one of $P_1$ , $P_2$ , . . . , $P_{i−1}$ ”.
Prove that $Pr(B_i) ≤ \frac{i-1}{d}$
I believe that $Pr(B_i)$ is equal to $1 - \frac{d(d-1)^{i-1}}{d^i}$. But, so far it is impossible for me to see how to prove the inequality.
Suppose the $i-1$ people $P_1 , P_2 , \ldots , P_{i−1}$ have $n$ distinct birthdays
$n \le i-1$ with equality only if they are all have different birthdays
So the probability of person $P_i$ having one of these birthdays too is $\mathbb P(B_i)=\dfrac n d \le \dfrac{i-1}d$