1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Apr 23, 2008 #1
    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 [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: Apr 23, 2008
  2. jcsd
  3. Apr 24, 2008 #2
    I believe this is right.
     
  4. Apr 24, 2008 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)
     
  5. Apr 25, 2008 #4
    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.
     
  6. Apr 25, 2008 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: [Recurrence Relation]three conscutive 0's in bit string
  1. Recurrence Relation (Replies: 1)

  2. Recurrence Relation (Replies: 3)

Loading...