Results 1 to 5 of 5

Math Help - Discrete math

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    2

    Discrete math

    Let an be the number of bit strings of length n (n = 1, 2, ...) that contain the string 00 (two consecutive zeroes).
    (a) Find a1, a2, a3, a4.
    (b) Find a recurrence relation for the sequence {an}.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Please take note an should be a subscript n

    Please take note an should be a subscript n

    Let an be the number of bit strings of length n containing two consecutive 0s. These an strings consist of:

    the strings starting with 1 --- the number is an-1
    the strings starting with 01 --the number is an-2
    the strings starting with 00 --the number is 3n−2
    Therefore, the recurrence relation is:
    an = an−1 + an−2 + 3n−2 , for n ≥ 3

    Initial conditions: a1 = 0, a2 =1
    a3 = a2 + a1 + 31 = 1 + 0 + 3 = 4
    a4 = a3 + a2 + 32 = 4 + 1 + 9 = 14
    Last edited by tester85; October 21st 2008 at 05:30 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,959
    Thanks
    1783
    Awards
    1
    Quote Originally Posted by skii View Post
    Let an be the number of bit strings of length n that contain the string 00 (two consecutive zeroes).
    (a) Find a1, a2, a3, a4
    (b)Find a recurrence relation for the sequence
    Quote Originally Posted by tester85 View Post
    Please
    Let an be the number of ternary strings of length n containing two consecutive 0s.
    Why were bit strings changed to ternary strings?
    The OP is clearly about bit strings.
    Moreover, I wonder if the word not was left out of the OP?
    “the number of bit strings of length n that do not contain the string 00”?
    That is a very nice recurrence relation! As stated it is not!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Thread updated. Thanks for pointing out the mistake. I hope it is correct now
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by skii View Post
    Let
    an be the number of bit strings of length n (n = 1, 2, ...) that contain the string

    00 (two consecutive zeroes).
    (a) Find a1, a2, a3, a4.


    Well obviously a_1=0, a_2=1.

    a_3=2, as the none zero bit bay be the first or last

    a_4= , well I will leave that to you, just list them and count.


    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Discrete Math Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 05:15 PM
  2. Help me, I am new to discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 06:15 PM
  3. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 8th 2007, 11:07 AM
  4. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: April 26th 2007, 09:49 AM
  5. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 01:01 AM

Search Tags


/mathhelpforum @mathhelpforum