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 stri

Bivariate numerical data
ANSWERED 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. 2021-03-08

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$$