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ⁿ.
So the probability that no two consecutive heads occur in n coin tosses is f(n) / 2ⁿ.

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, F₂ = 1, F_k = F_k−1 + F_k−2, for k > 2.
So F₃ = 2 and F₄ = 3, and therefore f(n) = F_n+2.

A closed form formula for the Fibonacci sequence is F_n = (Phiⁿ − phiⁿ) /,
where Phi = (1 + )/2 and phi = (1 − )/2 are the roots of the quadratic equation x² − x − 1 = 0.

Therefore the probability that no two consecutive heads appear in n tosses of a coin is F_n+2 / 2ⁿ = (Phiⁿ⁺² − phiⁿ⁺²) / 2ⁿ·.

Solution to puzzle 40: No consecutive heads

Further reading