A community for students.
Here's the question you clicked on:
 0 viewing
anonymous
 one year ago
refer to the sequence S where S subset of n denotes the number of nbit strings that do not contain the pattern 00. Show that S_n = f_(n+2,) n = 1, 2, …, where ƒ denotes the Fibonacci sequence.
anonymous
 one year ago
refer to the sequence S where S subset of n denotes the number of nbit 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

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Let's say we have a 2bit 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\))?

anonymous
 one year ago
Best ResponseYou've already chosen the best response.0Now suppose we have a 3bit string. How many strings \(1xx\) don't contain \(00\)? How many strings \(0xx\)? The 3bit strings starting with \(1\) is the same as the total number of 2bit strings, while the 3bit strings starting with \(0\) MUST be the same as the number of 2bit strings that started with \(1\) (otherwise we'd get a string with \(00\)). See where this is going?
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.