How is $e^{\frac{-k(k-1)}{2n}} \leq \frac{1}{2}$

Question

I was learning from the book Introduction to Algorithms (section 5.4.1) and came across the birthday paradox. This was the solution I saw:

$Pr\{B_k\} = 1. (1 -\frac{1}{n})(1-\frac{2}{n})...(1 - \frac{k-1}{n})$

$1 + x <= e^{x} (Inequality (3.12))$

So from Inequality (3.12), x= $\frac{-1}{n}$

$Pr\{B_k\} \leq e^{\frac{-1}{n}}e^{\frac{-2}{n}}...e^{\frac{-(k-1)}{n}} $

= $e^{\sum_{i=k}^{k-1}\frac{i}{n}}$

= $e^{\frac{-k(k-1)}{2n}}$

$\leq 1/2$

where n = 365 days and k is the number of people in the room.

Please can anyone explain to me how they end up having $1/2$

Answer 1

I expect the book is working out how many people have to be in a room for it to be more likely than not that two people in the room have the same birthday. For something to be more likely than not it has to have probability greater than 1/2. That means makes the probability of it not being the case must be less than (1 - 1/2) which is less than 1/2.