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!

Recurrence relation

  1. Nov 16, 2016 #1
    1. The problem statement, all variables and given/known data
    Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0s.

    2. Relevant equations


    3. The attempt at a solution
    Let ##a_n## count the number of ternary stings of length n that contain two consecutive 0s. Then, we can split the total number into mutually exclusive cases. If we start with 1 or 2, then we have ##a_{n-1}## in both cases. If we start with 01 or 02, then we have ##a_{n-2}## in both cases. If we start with 00, then we have ##3^{n-2}## possibilities for the other strings, since we already have two consecutive zeroes. Thus ##a_n = 2a_{n-1} + 2a_{n-2} + 3^{n-2}##.

    However, apparently the solution is ##a_n = 2a_{n-1} + 2a_{n-2} + 2^{n-2}##. Is this correct or is mine correct?
     
  2. jcsd
  3. Nov 16, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Perhaps they mean exactly one instance of 00, rather than one or more instances of 00. Under the latter (former) interpretation you (they) are correct.
     
  4. Nov 17, 2016 #3

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    No, it still doesn't make the book answer correct. Even though there must be no more pairs of consecutive zeroes, there can still be isolated ones.
     
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: Recurrence relation
  1. Recurrence Relation (Replies: 1)

  2. Recurrence Relation (Replies: 3)

  3. Recurrence relations (Replies: 3)

Loading...