Coin Flip. Topic: Probability/S&S. Level: AIME.

Problem: (2001 Putnam - A2) You have coins $ C_1, C_2, \ldots, C_n $. For each $ k $, $ C_k $ is biased so that, when tossed, it has probability $ \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 your answer as a rational function of $ n $.

Solution: As usual, we try it out. Let $ P_k $ be the probability that we have an odd number of heads after $ k $ tosses. We find that

$ P_1 = \frac{1}{3} $, $ P_2 = \frac{2}{5} $, $ P_3 = \frac{3}{7} $.

Now we guess that $ P_k = \frac{k}{2k+1} $, which we will prove by our favorite tool, induction. Suppose it is true for $ k $. On the $ (k+1) $th flip, if we previously had an odd number we want a tails and if we previously had an even number we want a heads. So

$ P_{k+1} = \frac{2k+2}{2k+3}P_k+\frac{1}{2k+3}(1-P_k) = \frac{1}{2k+3}+\frac{2k+1}{2k+3}P_k $.

Plugging in our induction hypothesis, we get

$ P_{k+1} = \frac{1}{2k+3}+\frac{2k+1}{2k+3} \cdot \frac{k}{2k+1} = \frac{k+1}{2k+3} $,

which is what we want. Hence we have

$ P_n = \frac{n}{2n+1} $.

QED.

--------------------

Comment: A classic probability recursion problem, reminiscent of some old AIME problems. It should not have been too difficult to notice the pattern and figure out that induction is the way to go. It also has ties to Dynamic Programming, one of the most interesting concepts in computer science, which is based on solving problems using the solutions of subproblems (in this case, less coins).

--------------------

Practice Problem: (1990 AIME - #9) A fair coin is to be tossed $10$ times. Let $ \frac{i}{j} $, in lowest terms, be the probability that heads never occur on consecutive tosses. Find $ i+j $.