recurrence relation

It has been sometimes I haven't replied any questions, and this question is fun, let me attempt it:

Denote
S(n) be the set of n-bit strings that does not contain 000 or 111.
A(n) be the number of strings in S that ends with 100
B(n) be the number of strings in S that ends with 001
C(n) be the number of strings in S that ends with 101
D(n) be the number of strings in S that ends with 010
E(n) be the number of strings in S that ends with 110
F(n) be the number of strings in S that ends with 011

It is obvious that:
A(3)=B(3)=C(3)=D(3)=E(3)=F(3)=1

And the recurrence relationship of these will be
A(n+1) = D(n) + E(n)
B(n+1) = A(n)
C(n+1) = D(n) + E(n)
D(n+1) = B(n) + C(n)
E(n+1) = F(n)
F(n+1) = B(n) + C(n)

I will explain one of them and the rest trivially follow. The number of n+1 bit strings that ends with 100 must have a prefix of a n-bit string that ends with 10, therefore we have A(n+1) =D(n) + E(n).

Now we simplify the relationship, 1st notice A=C and D=F, we will simply replace them.

A(n+1) = D(n) + E(n)
B(n+1) = A(n)
D(n+1) = B(n) + A(n)
E(n+1) = D(n)

Now we eliminate B and E as well.

A(n+1) = D(n) + D(n-1)
D(n+1) = A(n-1) + A(n)

We substitute and get
A(n+1) = A(n-1) + 2A(n-2) + A(n-3)
D(n+1) = D(n-1) + 2D(n-2) + D(n-3)

At this point, we also recognize A = D. Therefore
A(n+1) = A(n) + A(n-1)

And A(n) is really just the Fibonacci numbers.

2009-11-24 15:59:25 補充：
Add the last bits.

Since we know A = C = D = F and B(n+1) = A(n).
We also have A(n) = F(n-1), therefore B(n) = E(n) = F(n-2).
We have finally |S(n)| = 4F(n-1) + 2F(n-2) as the final solution.
If you wish, you can also say

S(n) = S(n-1) + S(n-2) as the recurrence relationship.