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\)