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!

Finding Recurrence Relation

  1. Dec 4, 2013 #1
    I am having difficulty knowing which "cases" include in the recurrence equation.

    My solution to problem in paint document.

    Cases 1 - 6:
    All cases contain strings of length n
    Let ak represent number of bit string of length k with a pair of consecutive 0s.

    For cases 1 and 2.
    an-1, k = n-1.

    1. Start with 0
    0_ _ ... _
    2. Start with 1
    1_ _ ... _

    For cases 3 - 5
    an-2, k = n-2.

    3. Start with 1 0
    1 0 _ ... _
    4. Start with 1 1
    1 1 _ ... _
    5. Start with 0 1
    0 1 _ ... _

    Case 6
    an-2 = 2n-2

    6. Start with 0 0
    0 0 _ ... _

    Therefore
    An = (sum of ak from case 1 and 2) + (sum of ak from case 3,4, and 5) + (ak from case 6) =
    2(an-1) + 3(an-2) + 2n-2

    Cases that "overlap"
    1 and 5: if second term of case 1 is 1
    1 and 6: if second term of case 1 is 0

    2 and 3: if second term of case 2 is 0
    2 and 4: if second term of case 2 is 1

    Therefore
    an = 2(an-1) - (an-2) + 2n-2 = An - 4(an-2)
     

    Attached Files:

    Last edited: Dec 4, 2013
  2. jcsd
  3. Dec 4, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I couldn't follow how you got your final equation from the various cases.
    But it's much simpler if you just consider three mutually exclusive cases instead of having to subtract out overlaps. What are the three cases?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Finding Recurrence Relation
  1. Recurrence Relation (Replies: 1)

  2. Recurrence Relation (Replies: 3)

Loading...