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)**