# Morning Socks Routine

Martha has to put on socks before leaving her house in the morning. She has a drawer in her bedroom which contains $$N$$ different pairs of socks. Martha starts pulling socks from the drawer one by one, and a soon as she gets a matching pair, she stops and departs for work. Find the expected value $$\mathbb{E}\left( X \right)$$ of the number of socks she has to pull every day from her drawer before she can leave her house.

The Ugly One
Let’s bruteforce the expected value:
$$\mathbb{E}\left( X \right) = \sum_i^N i \cdot p_i = 2 \cdot p_2 + 3 \cdot p_3 + … + (N + 1) \cdot p_{N + 1}$$ Where $$p_i$$ is the probability of her going to work after pulling out $$i$$ number of socks. It is obvious that $$p_1 = 0$$ since she will have only one sock at that moment, and that she is guaranteed to stop and have a matching pair after pulling $$N + 1$$ socks from the drawer.
Probability $$p_i$$ is conditional on survival $$1-p_{i-1}$$, i.e. reaching step $$i$$: $$p_i = (1 – p_{i-1}) \cdot r_i$$ Where $$r_i$$ is a probability of a match after pulling $$i$$-th sock: $$r_i = \frac{i – 1}{2N – (i – 1)}$$