Coin flip combinatorics problem

Consider the two scenarios:

1. Toss a coin $n$ times. Whatever the value of the first toss is, just record whether each of the subsequent $n-1$ tosses was the same as ($S$) or different to ($D$) its predecessor.

2. Take a different coin whose sides are labelled $S$ and $D$, and toss it $n-1$ times.

In both cases, each sequence of $n-1$ $S$s and $D$s is equally likely. There are however two ways of obtaining each such sequence in the first scenario (since we can obtain each sequence once by throwing a head first, and once by throwing a tail first). The point of this is that the event of getting three or more consecutive heads, or three or more consecutive tails, in the first scenario exactly corresponds to the event of getting two or more consecutive $S$s in the second scenario.

Working in the second scenario, we want to know how many sequences of $n-1$ tosses result in two or more consecutive $S$s. It is easier to count the sequences that do not. Let $x_m$ be the number of sequences of $m$ tosses of the relabelled coin that do not contain consecutive $S$s. Certainly $x_1=2$ and $x_2=3$. Suppose now that $m \ge 3$.

• It is clear the the number of sequences of $m$ tosses that do not contain consecutive $S$s and which start with a $D$ is just equal to $x_{m-1}$, the number of sequence of $m-1$ tosses that do not contain consecutive $S$s (just ignore the first toss);

• If the first toss is $S$, we need the second toss to be $D$ if we want to be $SS$-free. Thus the number of sequences of $m$ tosses that do not contain consecutive $S$s and which start with a $S$ is just equal to $x_{m-2}$.

Hence $x_m \,=\, x_{m-1} + x_{m-2}$ for all $m \ge 3$. From this it is clear that $x_m = F_{m+2}$ is the $(m+2)$nd Fibonacci number (starting the sequence $F_0=0$, $F_1=1$, etc. ).

We now interpret these results in the first scenario. The probability of getting three consecutive heads or three consecutive tails in $n$ throws is $1 - x_{n-1}2^{-(n-1)} = 1 - F_{n+1}2^{-(n-1)}$. Alternatively, the number of sequences of $n$ coin tosses which contain three consecutive heads or three consecutive tails $2^n - 2F_{n+1}$.

9/257

By "sequence of three consecutive heads" do you mean "sequence of exactly three consecutive heads" or "sequence of at least three consecutive heads?" For example, does HHHH count as a "sequence of three consecutive heads" or not?

Also, I'm having great difficulty understanding the purpose of your hint. Surely anyone capable of solving this problem already knows how to count the total number of possible outcomes of ten coin flips, and those who aren't so capable will not be helped at all by it! Are you trying to imply by a trivial hint that the problem has a trivial solution?