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

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:

1. It begins with a tail, and is followed by n−1 tosses with no consecutive heads; or
2. 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 F1 = 1, F2 = 1, Fk = Fk−1 + Fk−2, for k > 2.
So F3 = 2 and F4 = 3, and therefore f(n) = Fn+2.

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

Therefore the probability that no two consecutive heads appear in n tosses of a coin is Fn+2 / 2n = (Phin+2 − phin+2) / 2n·.