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!

[Discrete Math] Recurrence Relations

  1. Apr 16, 2006 #1
    Question:

    "Find a recurrence relation and initial conditions for the sequence {a sub n} if a sub n is the number of bit strings of length n that contain three consecutive 0's."

    So here's what I have so far...
    n > 3
    n = 4, 1000, 0001
    n = 5, 10000, 00001, 00010, 01000, 10001
    n = 6, 100000, 000001, 010000, 000010, 001000, 00100, 111000, 000111, 110001, 100011, 110000, 000011, 100001, 101000, 000101, 100010, 010001, ... I might have missed a few...

    Anyways here's what I see... As n increases the number of bit strings increases (almost exponentially), and the maximum number of 1's in the string is n-3. In n-6, you have 3x1's.

    That's all I have so far... And I don't know where else to go from here. So I would like some help with this.
     
  2. jcsd
  3. Apr 16, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You have to get a recurrence relation. What is a recurrence relation?
     
  4. Apr 16, 2006 #3
    "...a recurrence relation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms."
     
  5. Apr 16, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    So how would you try to write the number of permissible strings of length n in terms of the lengths of smaller strings?
     
  6. Apr 16, 2006 #5
    I don't understand what you mean... But from what I gather if you have the string 100000, this can be written as string 100 + string 000 (concatination)
     
  7. Apr 16, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You want to count the number of strings of length n. You need to figure out a way to relate this number to the number of strings of some smaller lengths. It's counting. (And it's concatenation.)

    Ie you need to work out some relation with a_n and a_{n-1} and almost certainly some other a_{m}, that is what a recurrence relation is.. I'm not going to do this for you, nor should anyone else. You need to work through it. And I'm reluctant to say more becuase I'd like you to work out the method you need to use to count these things.
     
  8. Apr 16, 2006 #7
    My final answer is something along the lines of...

    a_n = a_(n-1) + a_(n-2) + 2^(n-3)

    Since you have 3 cases...
    1 + a bit string of length n-1, the string has 3, 0's.
    01 + a bit string of length n-2, the string has 3, 0's.
    000 + a bit string of length n-3, and the string can be of any value since you have the 3, 0's.
     
  9. Apr 16, 2006 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    what happened to strings that start 001? but you certainly figured out the right method, well done.
     
  10. Apr 16, 2006 #9
    Good point!
    Case 4:
    001 + a bit string of length n-3, string has 3 0's.

    So it's:
    a_n = a_(n-1) + a_(n-2) + a_(n-3) + 2^(n-3)
     
  11. Apr 16, 2006 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    don't forget the initial conditions. or the three initial terms.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: [Discrete Math] Recurrence Relations
  1. Recurrence relation (Replies: 5)

Loading...