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

[master cherundo]

Homework Statement

Find a recurrence relation for the number of bit strings of length n that contain three consecutive $$0$$s.

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

 

[kamerling]

I believe this is right.

 

[Hurkyl]

Examples i ever seen is just discuss about bit strings of length n that does not have k bit strings.

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)

 

[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.

 

[Hurkyl]

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.

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.