Answer to puzzle 40: No consecutive heads

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

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 above probability can also be written as (Phiⁿ⁺² − phiⁿ⁺²) / 2ⁿ·.