What is the probability of an odd number of heads when tossing $n$ biased coins?

[Ackbach]

Here is this week's POTW:

-----

You have coins $C_1,C_2,\ldots,C_n$. For each $k$, $C_k$ is biased so that, when tossed, it has probability $\displaystyle \frac{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$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 272 - Jul 18, 2017

This was Problem A-2 in the 2001 William Lowell Putnam Mathematical Competition.

No one answered this week's POTW. The solution, attributed to Kiran Kedlaya and his associates, follows:

Spoiler

Let $P_n$ denote the desired probability. Then $P_1=1/3$, and, for $n>1$,
\begin{align*}
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}.
\end{align*}
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)$.