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

The Attempt at a Solution

Divide the bit strings into two condition: one that have three consecutive 0s, 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.