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

by fishynuggyyy   Last Updated August 11, 2018 03:20 AM

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!

Related Questions

Congruence if and only if Left and Right Congruence

Updated September 01, 2017 02:20 AM


Updated March 06, 2018 19:20 PM