Skip to main content.

Hint to puzzle 40: No consecutive heads

Observe that any sequence of heads and tails, of length two or more, is built up of a series of shorter subsequences.

Let f(n) be the number of sequences of length n with no two consecutive heads.
Using the above observation, establish a recurrence relation between f(n), f(n − 1), and f(n − 2).