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.

Question

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.

escumantsu · Accepted Answer

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=Zn−1+Zn−2+Zn−3

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

Answered question

Answer & Explanation

New Questions in College Statistics