Berkeley Math Circle Monthly Contest 5

Solution:

Let $P_n$ be the probability that an odd number out of the coins whose numbers are at most $n$ ($1 \leq n \leq 2015$) come up heads. For $2 \leq n \leq 2015$, there are two ways for this to happen: coin $n$ is tails and an odd number of the preceding coins are heads, or coin $n$ is heads and an even number of the preceding coins are heads. So we have a recursion
$$\begin{aligned} P_n & = \left(1 - \frac{1}{2n^2}\right) P_{n-1} + \frac{1}{2n^2} (1 - P_{n-1}) \\ & = \frac{2n^2 P_{n-1} - 2P_{n-1} + 1}{2n^2} \\ & = \frac{2(n^2 - 1) P_{n-1} + 1}{2n^2}. \end{aligned}$$
If we subtract $1/2$ from each side, we have the factorization
$$P_n - \frac{1}{2} = \frac{n^2 - 1}{n^2} \left(P_{n-1} - \frac{1}{2}\right)$$
Now, using the initial value $P_1 = 0$, we have
$$\begin{aligned} P_{2015} - \frac{1}{2} & = -\frac{1}{2} \cdot \prod_{n=2}^{2015} \frac{n^2 - 1}{n^2} \\ & = -\frac{1}{2} \cdot \prod_{n=2}^{2015} \frac{(n-1)(n+1)}{n \cdot n} \\ & = -\frac{1}{2} \cdot \frac{(1 \cdot 2 \cdots 2014)(3 \cdot 4 \cdots 2016)}{(2 \cdot 3 \cdots 2015)(2 \cdot 3 \cdots 2015)} \\ & = -\frac{1}{2} \cdot \frac{1 \cdot 2016}{2015 \cdot 2} \\ & = -\frac{504}{2015} \end{aligned}$$
and thus
$$P_{2015} = \frac{1}{2} - \frac{504}{2015} = \frac{1007}{4030}$$