0
$\begingroup$

Consider binary strings with $n$ digits (for example, if $n=4$, some of the possible strings are 0011, 1010, 1101, etc.)

Let $z_{n}$ be the number of binary strings of length n that do not contain the substring 000. Find a recurrence relation for $z_{n}$.

I've looked at alternative solutions for the same case but with ternary strings and bit strings but I've failed to draw an understanding of how to solve this problem. Please help!

$\endgroup$
5
  • 1
    $\begingroup$ Could you give more details how the pattern looks like ? $\endgroup$ Commented Aug 11, 2018 at 3:00
  • $\begingroup$ isn't a bit string same as a binary one? $\endgroup$ Commented Aug 11, 2018 at 3:13
  • $\begingroup$ That's all the information the question provides, sorry! $\endgroup$ Commented Aug 11, 2018 at 3:24
  • $\begingroup$ @coffeemath when I looked it up online it said they differed! But I was also quite confused so I am not 100% certain. $\endgroup$ Commented Aug 11, 2018 at 3:24
  • $\begingroup$ Well, your quoted part of the question (with the examples given) makes it clear what it is desired to count. So whether one calls them bit strings or binary ones doesn't seem to matter. $\endgroup$ Commented Aug 11, 2018 at 9:49

1 Answer 1

Reset to default
1
$\begingroup$

A good string can only start with 1, 01, 001 and after any of these it becomes the same question but one has to add 1,2, or 3 to the count.

This approach can be made into a recurrence but I'll leave that to you.

Edit: no adding to the count is appropriate, since e.g. a string starting with 1 gives f(n-1) strings for that case, etc.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.