You have coins C1, C2, · · · , Cn. For each k, coin Ck 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.
Source:
Putnam 2001
(In reply to
Analytic solution by Larry)
let p(k) be the probability of having an odd number of heads. We want to prove p(k)=k/(2k+1)
Our base case is k=1:
1/3 chance of coin C1 is heads, and 2/3 chance of tails. Then the odds of an odd number of heads is 1/3, which is satisfied by evaluating p(1) = 1/(2*1+1) = 1/3
Base case established.
So now to the inductive step. Assume the formula p(k) is true for k coins. Then C_k+1 coin has a 1/(2k+3) chance of coming up heads and (2k+2)/(2k+3) chance of coming up tails.
Then the probability of having an odd total coins out of k+1 coins being heads can be expressed as the sum of adding tails to an odd number of heads from the p(k) or adding heads to an even number of heads 1-p(k):
p(k+1) = p(k)*[(2k+2)/(2k+3))] + [1-p(k)]*[1/(2k+3)]
Now substitute p(k)=k/(2k+1):
p(k+1) = [k/(2k+1)]*[(2k+2)/(2k+3))] + [1-k/(2k+1)]*[1/(2k+3)]
p(k+1) = [2k*(k+1)]/[(2k+1)*(2k+3)] + [k+1]/[(2k+1)*(2k+3)]
p(k+1) = [(2k+1)*(k+1)]/[(2k+1)*(2k+3)]
p(k+1) = (k+1)/(2k+3)
This result is indeed p(k) evaluated at k+1, so our induction holds and the formula for p(k) is k/(2k+1).
re: Analytic solution - proof
