• Support PF! Buy your school textbooks, materials and every day products Here!

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

1. Homework Statement
Find a recurrence relation for the number of bit strings of length n that contain three consecutive [tex]0[/tex]s.



3. The Attempt at a Solution
Divide the bit strings into two condition: one that have three consecutive [tex]0[/tex]s, another that does not. Let [tex]x_i[/tex] denote the bit strings of length n that fulfill that condition. Then, we can get [tex]x_i[/tex] by adding a 0 or a 1 to [tex]x_{i-1}[/tex]. But, there is another bit strings that included in [tex]x_i[/tex]. That is by adding [tex]1000[/tex] string to bit strings of length [tex]n-3[/tex] that does not have three consecutive 0s. This is can be write by [tex]2^{n-4}-x_{n-4}[/tex]. So, we get [tex]x_n=2x_{n-1}-x_{n-4}+2^{n-4}[/tex].
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:

Answers and Replies

454
0
I believe this is right.
 
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
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)
 
My friends has different approach in solving this, but actually these two relation produce same output for [tex]x_7[/tex]
The base case is questioned after this problem. :wink:
The assignment has been submitted.
 
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
My friends has different approach in solving this, but actually these two relation produce same output for [tex]x_7[/tex]
The base case is questioned after this problem. :wink:
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.
 

Related Threads for: [Recurrence Relation]three conscutive 0's in bit string

  • Last Post
Replies
3
Views
625
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
2
Views
708
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
14
Views
877
Replies
2
Views
716
  • Last Post
Replies
5
Views
366
Top