A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

sh3lsh

  • one year ago

Find a recurrence relation for the number of binary strings of length “n” that do not contain three of the same number in a row. How do I approach this problem?

  • This Question is Closed
  1. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I'd start off by creating the sequence that counts the number of strings that DO contain three of the same number in a row. Call this sequence \(b_n\), then clearly \(b_1,b_2=0\), while \(b_3=2\) (since you can have \(111\) or \(000\)). Then whatever this sequence will be, let \(a_n\) denote the number of strings that DO NOT contain the three-in-a-row pattern, so \(a_n=2^n-b_n\). All this to say you'd find a closed form for \(a_n\), then make a recurrence relation out of that.

  2. sh3lsh
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    I've got to close this question and ask an easier one so I understand the foundation of recurrence relationships. I'm totally confused.

  3. sh3lsh
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Could you continue to help me on this question?

  4. anonymous
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Actually, here's a more direct way of finding what you want. Suppose \(x\) is a binary string of length \(n\). This string can end in \(1\), \(0\), \(11\), or \(00\). (We're basically considering the cases where the last two digits are distinct or the same consecutive digit.) So letting \(a_n\) be the total number of possible \(n\)-length binary strings without \(111\) or \(000\), we'll let \(b_n\) denote the number of such strings that end in \(1\), \(c_n\) the number of such strings ending in \(0\), \(d_n\) for those ending in \(11\), and \(e_n\) for those ending in \(00\). In other words, we have the following relation: \[a_n=b_n+c_n+d_n+e_n\] What we want to do is write \(b_n,c_n,d_n,e_n\) in terms of previous terms in the sequence \(\{a_n\}\). Does that make sense so far?

  5. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.