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

Ernstfalld

Ernstfalld

Answered question

2021-03-07

Consider binary strings with n digits (for example, if n=4, some of the possible strings are 0011,1010,1101, etc.)
Let Zn be the number of binary strings of length n that do not contain the substring 000
Find a recurrence relation for Zn
You are not required to find a closed form for this recurrence.

Answer & Explanation

escumantsu

escumantsu

Skilled2021-03-08Added 98 answers

Consider such a sequence of n digits.
If the first digit is 1, then we must not have a substring 000 in the remaning part of this sequence. Thus, we have Zn-1 such sequences.
If the first digit is 0, then we look at the second digit. If the second digit is 1, then this sequence starts with 01, meaning that we must not have a substring 000 in the remaning n—2 digits. Therefore, there are Zn-2 such sequences.
If the second digit is 0, then this sequence starts with 00. This means that the third digit must be 1 (otherwise, we would have 000 in this sequence). Therefore, this sequence starts with 001, meaning that we must not have 00 asa substring in the remaining n —3 digits. Thus, there are Zn-3 such sequences.
This covers all cases. Therefore, the recurrence relation is Zn=Zn1+Zn2+Zn3

Do you have a similar question?

Recalculate according to your conditions!

New Questions in College Statistics

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?