In how many n-sequences of flips of a coin is there never two heads in a row? Or how many n-sequences of H’s and T’s do not contain “HH”? For each positive integer n, let f(n) denote the number of...

In how many n-sequences of flips of a coin is there never two heads in a row? Or how many n-sequences of H’s and T’s do not contain “HH”? For each positive integer n, let f(n) denote the number of such sequences. The list of all two-sequences of H’s and T’s that don’t contain “HH” is

HT TH TT; so f(2) = 3:

(a) List all three-sequences of H’s and T’s that don’t contain “HH”.

(b) List all four-sequences of H’s and T’s that don’t contain “HH”.

(c) Find a recurrence equation satisfied by the sequence f.