Skip to main content.

Answer to puzzle 40: No consecutive heads

The probability that no two consecutive heads appear in n tosses of a coin is Fn+2 / 2n,
where Fn is the Fibonacci sequence, defined by the recurrence relation Fn = Fn−1 + Fn−2, for n > 2, with F1 = F2 = 1.

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

Therefore the above probability can also be written as (Phin+2 − phin+2) / 2n·root 5.