[Recurrence Relation]three conscutive 0's in bit string

1. Apr 23, 2008

master cherundo

1. The problem statement, all variables and given/known data
Find a recurrence relation for the number of bit strings of length n that contain three consecutive $$0$$s.

3. The attempt at a solution
Divide the bit strings into two condition: one that have three consecutive $$0$$s, another that does not. Let $$x_i$$ denote the bit strings of length n that fulfill that condition. Then, we can get $$x_i$$ by adding a 0 or a 1 to $$x_{i-1}$$. But, there is another bit strings that included in $$x_i$$. That is by adding $$1000$$ string to bit strings of length $$n-3$$ that does not have three consecutive 0s. This is can be write by $$2^{n-4}-x_{n-4}$$. So, we get $$x_n=2x_{n-1}-x_{n-4}+2^{n-4}$$.
Is my recurrence relation right?
Examples i ever seen is just discuss about bit strings of length n that does not have k bit strings..

Thank you

master cherundo

Last edited: Apr 23, 2008
2. Apr 24, 2008

kamerling

I believe this is right.

3. Apr 24, 2008

Hurkyl

Staff Emeritus
Well, there's an easy relationship between this kind of question and the one you are solving here. BTW, you forgot to specify the base case for your recursion. Incidentally, did you do any sanity checking? (e.g. compute the first few values of x directly)

4. Apr 25, 2008

master cherundo

My friends has different approach in solving this, but actually these two relation produce same output for $$x_7$$
The base case is questioned after this problem.
The assignment has been submitted.

5. Apr 25, 2008

Hurkyl

Staff Emeritus
I had a different way too. I checked up to x(8), and I agree with yours as well. I'm used to recursively defining several sequences in parallel:

A sequence counting how many sequences do not have 000, and end in 1.
A sequence counting how many sequences do not have 000, and end in 10.
A sequence counting how many sequences do not have 000, and end in 100.
A sequence counting how many sequences have 000.

It's more tedious, but it does have the advantage of being formulaic, and you can always do some linear algebra / difference equation solving to simplify it, if you want.