A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

refer to the sequence S where S subset of n denotes the number of n-bit strings that do not contain the pattern 00. Show that S_n = f_(n+2,) n = 1, 2, …, where ƒ denotes the Fibonacci sequence.

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

    Let's say we have a 2-bit string. If it starts with \(1\) (i.e. the string is \(1x\) where \(x\) is a \(1\) or \(0\)), how may possible strings are there that don't contain \(00\)? What if the string starts with \(0\) (\(0x\))?

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

    Now suppose we have a 3-bit string. How many strings \(1xx\) don't contain \(00\)? How many strings \(0xx\)? The 3-bit strings starting with \(1\) is the same as the total number of 2-bit strings, while the 3-bit strings starting with \(0\) MUST be the same as the number of 2-bit strings that started with \(1\) (otherwise we'd get a string with \(00\)). See where this is going?

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