Results 1 to 2 of 2

Math Help - recurrence relation bit strings

  1. #1
    Member
    Joined
    Dec 2008
    Posts
    86

    recurrence relation bit strings

    hello!
    well I need help with this problem:

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

    ok the answer is:

    Let
    sn be the number of n-bit strings that contain three consecutive zeros. Such strings can start with
    1 (there are
    sn1 of these), or with 01 (there are sn2 of these), or with 001 (there are sn3 of these), or

    with 000 (there are 2
    n3 of these). Therefore sn = sn1 + sn2 + sn3 + 2n3, for n  3.

    http://www.ics.uci.edu/~stasio/fall07/6D/sol8.pdf

    Ok but can someone explain to me why did they say: such strigns can start with 1,01,001 or 000?
    from where did they get these?

    thank you
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jan 2009
    Posts
    56
    These are all the four possibilities for creating this sequence.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 16th 2010, 06:39 AM
  2. Recurrence Relation Q
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 30th 2009, 11:57 PM
  3. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 06:20 PM
  4. Recurrence Relation Help
    Posted in the Calculus Forum
    Replies: 0
    Last Post: December 7th 2008, 08:49 AM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 7th 2008, 11:06 PM

Search Tags


/mathhelpforum @mathhelpforum