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 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
  1. ganeshie8
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    The 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\)

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

    Let \(a_n\) denote the number of \(n\) bit strings that do not have two consecutive 0's

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

    If the string ends in \(1\), then the \(n-1\)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_{n-1}\) |dw:1434309606750:dw|

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

    If the string ends in \(0\), then the \(n-1\)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_{n-2}\) |dw:1434309743465:dw|

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

    So the desired recurrence relation is \[\large a_{n}~~=~~a_{n-1}+a_{n-2}\]

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

    see if you can work the initial conditions

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

    \[a_{1} = 2 \\ 0 \: and \: 1 \\ a_{2} = 3 \\ 11, 01, 10 \\ correct? \]

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

    Looks good!

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

    You'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(n-3). Would you have any idea why one would such a thing?

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

    http://mathfaculty.fullerton.edu/sannin/teaching/471-fall14/GroupWork07-solns.pdf

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

    \(2^n\) comes very naturally wgen working with binary strings because the total number of strings of length \(n\) is \(2^n\)

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

    Let 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. ?

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

    Let me attempt

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

    In this case, would I separate the cases into where it ends with a 1, 10, and 00?

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

    use the original problem

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

    Oh, so still ending with a 1 and ending with a 0?

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

    Let \(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

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

    since total bit strings of length \(n\) is \(2^n\), do we have \[a_n+b_n = 2^n\] ?

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

    Is that a question? I think that's true.

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

    Yes, that means \(a_n = 2^n-b_n\) plug that in earlier recurrence relation

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

    Why would you do that? We already have \[a_{n}\] Could we just do \[b_{n} = 2^{k}-(a_{n-1} + a_{n-2})\]

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

    we can do that, but that is not a proper recurrence relation

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

    we want to have a single sequence in a recurrence relation (all b_n s)

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

    don't want a_n s

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

    replace \(a_{n-1}\) and \(a_{n-2}\) also

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

    How?

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

    Unfortunately, I must leave. Thanks for helping me through this much!

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

    \(a_{n-1}~~=~~2^{n-1}-b_{n-1}\)

  29. 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.