# Solution to puzzle 40: No consecutive heads

A fair coin is tossed n times. What is the probability that no two consecutive heads appear?

Let f(n) be the number of sequences of heads and tails, of length n, in which two consecutive heads do not appear.

The total number of possible sequences from n coin tosses is 2^{n}.

So the probability that no two consecutive heads occur in n coin tosses is f(n) / 2^{n}.

By enumeration, f(1) = 2, since we have {H, T}, and f(2) = 3, from {HT, TH, TT}.

We then derive a recurrence relation for f(n), as follows.

A sequence of n > 2 coin tosses has no consecutive heads if, and only if:

- It begins with a tail, and is followed by n−1 tosses with no consecutive heads; or
- It begins with a head, then a tail, and is followed by n−2 tosses with no consecutive heads.

These two possibilities are mutually exclusive, so we have f(n) = f(n−1) + f(n−2).

This is simply the Fibonacci sequence, shifted forward by two terms.

The Fibonacci sequence is defined by the recurrence equation F_{1} = 1, F_{2} = 1, F_{k} = F_{k−1} + F_{k−2}, for k > 2.

So F_{3} = 2 and F_{4} = 3, and therefore f(n) = F_{n+2}.

A closed form formula for the Fibonacci sequence is F_{n} = (Phi^{n} − phi^{n}) /,

where Phi = (1 + )/2 and phi = (1 − )/2 are the roots of the quadratic equation x^{2} − x − 1 = 0.

Therefore the probability that no two consecutive heads appear in n tosses of a coin is F_{n+2} / 2^{n} = (Phi^{n+2} − phi^{n+2}) / 2^{n}·.

## Further reading

- Fibonacci Numbers and the Golden Section
- Phi: That Golden Number
- Fibonacci Number
- Golden Ratio

Source: Traditional

Back to top