A community for students.
Here's the question you clicked on:
 0 viewing
sh3lsh
 one year ago
Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s.
I'm lost on how to start this.
sh3lsh
 one year ago
Find a recurrence relation and give initial conditions for the number of bit strings of length n that do not have two consecutive 0s. I'm lost on how to start this.

This Question is Closed

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2The number of \(n\) bit binary strings can be thought of as two sets : 1) Strings that end in \(1\) 2) Strings that end in \(0\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Let \(a_n\) denote the number of \(n\) bit strings that do not have two consecutive 0's

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2If the string ends in \(1\), then the \(n1\)th bit could be either \(0\) or \(1\) so the number of \(n\) bit strings that end in \(1\) and do not have two consecutive \(0\)'s are \(a_{n1}\) dw:1434309606750:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2If the string ends in \(0\), then the \(n1\)th bit must be\(1\), consequently the number of \(n\) bit strings that end in \(10\) and do not have two consecutive \(0\)'s are \(a_{n2}\) dw:1434309743465:dw

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2So the desired recurrence relation is \[\large a_{n}~~=~~a_{n1}+a_{n2}\]

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2see if you can work the initial conditions

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1\[a_{1} = 2 \\ 0 \: and \: 1 \\ a_{2} = 3 \\ 11, 01, 10 \\ correct? \]

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1You're great! Thanks! Can I ask you a quick question though? Often when I look at recurrence relationship answers, they have a(n) being something along of the lines of 2^ a(n3). Would you have any idea why one would such a thing?

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1http://mathfaculty.fullerton.edu/sannin/teaching/471fall14/GroupWork07solns.pdf

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2\(2^n\) comes very naturally wgen working with binary strings because the total number of strings of length \(n\) is \(2^n\)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Let me ask you a question. In light of the original problem, can you work a recurrence relation for the number of bit strings of length n that CONTAIN two consecutive 0s. ?

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1In this case, would I separate the cases into where it ends with a 1, 10, and 00?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2use the original problem

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1Oh, so still ending with a 1 and ending with a 0?

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Let \(a_n\) represents number of bit strings of length \(n\) that DO NOT have two consecutive 0's Let \(b_n\) represents number of bit strings of length \(n\) that CONTAIN two consecutive 0's

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2since total bit strings of length \(n\) is \(2^n\), do we have \[a_n+b_n = 2^n\] ?

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1Is that a question? I think that's true.

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2Yes, that means \(a_n = 2^nb_n\) plug that in earlier recurrence relation

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1Why would you do that? We already have \[a_{n}\] Could we just do \[b_{n} = 2^{k}(a_{n1} + a_{n2})\]

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2we can do that, but that is not a proper recurrence relation

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2we want to have a single sequence in a recurrence relation (all b_n s)

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2replace \(a_{n1}\) and \(a_{n2}\) also

sh3lsh
 one year ago
Best ResponseYou've already chosen the best response.1Unfortunately, I must leave. Thanks for helping me through this much!

ganeshie8
 one year ago
Best ResponseYou've already chosen the best response.2\(a_{n1}~~=~~2^{n1}b_{n1}\)
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.