A community for students.
Here's the question you clicked on:
 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?
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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0I'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 threeinarow pattern, so \(a_n=2^nb_n\). All this to say you'd find a closed form for \(a_n\), then make a recurrence relation out of that.

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.0I've got to close this question and ask an easier one so I understand the foundation of recurrence relationships. I'm totally confused.

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.0Could you continue to help me on this question?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Actually, 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?
Ask your own question
Sign UpFind more explanations on OpenStudy
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
 Engagement 19 Mad Hatter
 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.