Putnam 2001, Problem A-2

You have coins $C_1, C_2, \ldots, C_n$. For each $k$, $C_k$ is biased so that, when tossed, it has probability $1/(2k+1)$ of falling heads. If the $n$ coins are tossed, what is the probability that the number of heads is odd? Express the answer as a rational function of $n$.

Solution:
Let $P_n$ denote the desired probability. Then $P_1 = 1/3$, and, for $n > 1$,
$$P_n = \left(\frac{2n}{2n+1}\right)P_{n-1} + \left(\frac{1}{2n+1}\right)(1-P_{n-1})$$
$$= \left(\frac{2n-1}{2n+1}\right)P_{n-1} + \frac{1}{2n+1}.$$

The recurrence yields $P_2 = 2/5$, $P_3 = 3/7$, and by a simple induction, one then checks that for general $n$ one has $P_n = n/(2n+1)$.

Note: Richard Stanley points out the following noninductive argument. Put $f(x) = \prod_{k=1}^n (x+2k)/(2k+1)$; then the coefficient of $x^i$ in $f(x)$ is the probability of getting exactly $i$ heads. Thus the desired number is $(f(1) - f(-1))/2$, and both values of $f$ can be computed directly: $f(1) = 1$, and
$$f(-1) = \frac{1}{3} \times \frac{3}{5} \times \cdots \times \frac{2n-1}{2n+1} = \frac{1}{2n+1}.$$