Finding a Recurrence Relation for a binary string with n digits that do not contain 000

Question

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!

Answer 1

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.