Inductive way to show that probability of getting odd number of coins is $n/(2n+1)$ Here is a problem from the Putnam competition:

We have the 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 showing heads. If $n$ coins are tossed, what is the probability that the number of heads is odd?

Now, I figured out the answer should be $n/(2n+1)$ through engineers' induction:

*

*$C_1$: We have$${1\over3}$$

*$C_1, C_2$: We have$${{2 + 4}\over{3(5)}} = {2\over5}$$

*$C_1, C_2, C_3$: We have$${{(4(6)+ 2(6) + 2(4)) + 1}\over{3(5)(7)}} = {3\over7}$$

*$C_1, C_2, C_3, C_4$: We have$${{(4(6)(8) + 2(6)(8) + 2(4)(8) + 2(4)(6)) + (2 + 4 + 6 + 8)}\over{3(5)(7)(9)}} = {4\over9}$$
At this point I concluded that $n/(2n+1)$ must be the answer. However, I don't know how to complete the inductive step here. Can anyone help specifically with that?
Obviously since this is a Putnam problem there exists a very clever solution, see here:
https://prase.cz/kalva/putnam/psoln/psol012.html

Answer: $n/(2n+1)$.
Consider the expansion of$$(2/3 - 1/3)(4/5 - 1/5)(6/7 - 1/7) ... (2n/((2n+1) - 1/(2n+1)).$$The negative terms correspond to an odd number of heads. So the product is just prob even $-$ prob odd. But the product telescopes down to $1/(2n+1)$. Obviously prob even $+$ prob odd $= 1$, so prob odd $= (1 - 1/(2n+1))/2 = n/(2n+1)$.

However, I am looking for a way to complete a straightforward induction with an inductive step and not a far too clever solution most people could not come up with.
 A: Either an even number of heads in the first $n$, and a head on the $n+1$th, or an odd number of heads in the first $n$ and a tail on the last one.  The probability of an even number of heads is one minus the probability of an odd number of heads.
$$Pr(odd,n+1)=(1-Pr(odd,n))\frac1{2n+3}+Pr(odd,n)\frac{2n+2}{2n+3}$$
A: To conclude by induction, note that there are two paths to victory.  Either you have thrown an even number of Heads up to the $(n-1)^{st}$ stage and then you throw another $H$, or you have thrown an odd number, and then throw $T$.
Thus the answer is $$\left(1-\frac {n-1}{2n-1}\right)\times  \frac 1{2n+1}+\left(\frac {n-1}{2n-1}\right)\times \left(1-\frac 1{2n+1}\right)=\frac n{2n+1}$$ as desired.
A: I cannot resist the following generating function solution, which is straightforward if you are familiar with the area.
The probability generating function for the number of heads on the $i^{th}$ coin is $(\frac1{2i+1}x+\frac{2i}{2i+1})$. Therefore, the p.g.f. for the total number of heads is equal to
$$
f(x):=\left(\frac13x+\frac23\right)\left(\frac15x+\frac23\right)\cdots\left(\frac1{2k+1}x+\frac{2k}{2k+1}\right)=\frac{(x+2)(x+4)\cdots (x+2k)}{3\cdot 5\cdots (2k+1)}
$$
That is, $f(x)=\sum_{i=0}^kp_ix^i$, where $p_i$ is the probability of getting exactly $i$ heads.
To extract the sum of the odd coefficients of this only, we use the classic trick of $\frac12(f(1)-f(-1))$. In this case, this works out exactly to $$\frac12\cdot{(2k+1)!!-(2k-1)!!\over (2k+1)!!}=\frac12\left(1-\frac 1{2k+1}\right).\color{#0d0}{\checkmark}$$
