What is the probability that you will see an odd number of heads? You have $100$ biased coins. The probabilities of seeing heads when you toss these coins are equal to $1/3$, $1/5$, $1/7$, $1/9$, and so on, up to $1/201$ for the last coin (in general, for the $k$-th coin, the probability is $\frac{1}{2k+1}$. Suppose that you toss all these coins at the same time. What is the probability that you will see an odd number of heads?
Can someone help me figure out where to start with this, please? Thank you!
 A: Hint: Consider the generating function
$$ f(x) = \prod ( \frac{ 2k}{2k+1} + \frac{1}{2k+1} x)$$
The coefficient of $x^n$ gives you the probability that there are $n$ heads.
Hint: Let's find the sum of coefficient of even powers. This is equal to
$$ \frac{ f(1) + f(-1) } { 2}$$
Hint: $f(1) = 1$.
Hint: $f(-1) = \frac{ 1}{201} .$
Hence, conclude that the answer is $\frac{100}{201}$.
A: To elaborate more on Ross's recurrence, let there be $n$ coins in general and denote $H_n$ the probability of getting an odd number of heads. Clearly, $P_1=1/3$. I claim that
$$
H_n=(1-\frac{1}{2n+1})H_{n-1}+\frac{1}{2n+1}(1-H_{n-1}).
$$
The first term above is just getting tails in your $n^{th}$ shot and getting an odd number of heads in the $n-1$ before, and the second term is just the opposite.
Solving this recurrence relation yields $H_n=n/(2n+1)$, and you are looking for $H_{100}=100/201$.
A: You can calculate it easily in a spreadsheet.  In column A put the odd numbers from $3$ to $201$.  The chance you get a odd number of heads from the first coin is $1/3$, which you can write in B1 as $=1/A1$ and the chance you get an even is $(1-1/3)$, which you can write in Ca as $=1-1/A1$.  The chance you have an odd number from the first two coins is $(1/3)*(1-1/5)+(1-1/3)*(1/5)$, which you can write in B2 as $=B1*(1-1/A2)+C1*1/A2$  Figure out C2, copy down, and you find the probability of an odd number is about $0.497512438$  Mathematica will give you the exact rational result from a similar approach.  The important thing is to forget what you don't need to know.  When you get to the last coin, you don't care if you have $2, 8, 16$ or however many heads, only if you have an even number.
We can give an induction and recurrence relation approach.  Let $P(n)$ be the chance that you have an odd number of heads after $n$ tosses.  We would like to prove that $P(n)=\frac n{2n+1}$  As above, the recurrence is $P(n+1)=\frac 1{2n+3}(1-P(n))+\frac {2n+2}{2n+3}P(n)$  The base case is $P(1)=\frac 13$, which satisfies the desired relation.  Assume $P(k)=\frac k{2k+1}$  Then $$P(k+1)=\frac 1{2k+3}(1-P(k))+\frac {2k+2}{2k+3}P(k)\\=\frac 1{2k+3}\frac {k+1}{2k+1}+\frac{2k+2}{2k+3}\frac k{2k+1}\\\frac{(k+1)(2k+1)}{(2k+1)(2k+3}\\=\frac {k+1}{2k+3}$$ and we are done
