Results 1 to 7 of 7

Math Help - recurrence relation problem!

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    7

    recurrence relation problem!

    hi i am trying to solve this recrrence relation is tough!!
    given this question, i had no idea how to define the condition to start!
    can someone help me!!? I understand is an-1 for different cases !

    A string that contains only 0s, 1s, 2s and 3s is called a quaternary string.

    i) Find a recurrence relation for the number of quaternary strings that do not contain two consecutive zeros.

    ii)Solve the recurrence relation
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by yrlim1 View Post
    A string that contains only 0s, 1s, 2s and 3s is called a quaternary string.
    i) Find a recurrence relation for the number of quaternary strings that do not contain two consecutive zeros.
    Let Q_n be the number of quaternary strings of length n that do not contain two consecutive zeros.
    Do you understand that Q_1=4~\&~Q_2=15~? How and why?
    Now how would you count Q_3~?
    Here is a hint: ‘how many in Q_2 end in a zero"?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    7
    Quote Originally Posted by Plato View Post
    Let Q_n be the number of quaternary strings of length n that do not contain two consecutive zeros.
    Do you understand that Q_1=4~\&~Q_2=15~? How and why?
    Now how would you count Q_3~?
    Here is a hint: ‘how many in Q_2 end in a zero"?
    hmm how come Q2 have 15? so much? i thought is mean
    Q1
    11
    10
    01
    considering all the non-zero case for 1?

    Q2
    22
    21
    12

    someting like that??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by yrlim1 View Post
    hmm how come Q2 have 15? so much? i thought is mean
    Q1
    11
    10
    01
    considering all the non-zero case for 1?
    Q2
    22
    21
    12
    No, the strings that Q_1 counts are 0,1,2,3.

    The strings in Q_2 are of length two and they are
    01,02,03,10,11,12,13,20,21,22,23,30,31,32,33.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    May 2011
    Posts
    7
    Quote Originally Posted by Plato View Post
    No, the strings that Q_1 counts are 0,1,2,3.

    The strings in Q_2 are of length two and they are
    01,02,03,10,11,12,13,20,21,22,23,30,31,32,33.
    oh!
    Q3 would be
    001
    002
    003
    110
    111
    112
    113
    220
    221
    222
    223
    330
    331
    332
    333

    and we have to for Q4 also?
    how about the occurence of 000? or 00 ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,617
    Thanks
    1581
    Awards
    1
    Quote Originally Posted by yrlim1 View Post
    oh!
    Q3 would be
    001
    002
    003
    110
    111
    112
    113
    220
    221
    222
    223
    330
    331
    332
    333
    and we have to for Q4 also?
    how about the occurence of 000? or 00 ?
    You sir/madam are simply fishing for an answer!
    You will not get such an answer from me.
    Show us some of your own work!
    Last edited by Plato; May 10th 2011 at 02:45 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,902
    Thanks
    329
    Awards
    1
    Quote Originally Posted by yrlim1 View Post
    oh!
    Q3 would be
    001
    002
    003
    110
    111
    112
    113
    220
    221
    222
    223
    330
    331
    332
    333

    and we have to for Q4 also?
    how about the occurence of 000? or 00 ?
    Read your source materials, look up information on the net...whatever you need to do. Even I can tell that this answer is incorrect and I don't even know the topic! Put some work into it and post your attempt.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2011, 06:45 AM
  2. Population recurrence relation problem.
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 14th 2011, 04:08 AM
  3. Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 10th 2010, 02:41 PM
  4. Recurrence Relation problem (URGENT)
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 20th 2010, 03:04 PM
  5. Recurrence relation problem
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 10:23 AM

Search Tags


/mathhelpforum @mathhelpforum