How many sequences of coin flips of length n have no appearance of 2 or more heads in a row?
Let T(n) be the number of sequences of length n that end with Tails and do not have 2 consecutive heads.
Let H(n) be the number of sequences of length n that end with Heads and do not have 2 consecutive heads.
Let G(n) be the total number of sequences, ie. T(n) + H(n)
We can form an acceptable sequence of length n + 1 in one of two ways:
By adding a Tail to the end of any acceptable sequence of length n.
By adding a Head to the end of any acceptable sequence of length n that ends in Tails.
So,
T(n) = T(n-1) + H(n-1)
H(n) = T(n-1)
initial conditions are
T(1) = 1 (only sequence is T)
H(1) = 1 (only sequence is H)
So, the table looks as follows:
n T(n) H(n) G(n)
-- --- --- -----
1 1 1 2
2 2 1 3
3 3 2 5
4 5 3 8
5 8 5 13
So, all the sequences are Fibonacci, F(n)!
H(n) = F(n)
T(n) = F(n+1)
G(n) = F(n+2)
An old Friend (spoiler)