How many binary numbers of length $n$ do not contain the substring $000$? Denote this number by $Z_n$; find a relationship between $Z_n$, $Z_{n-1}$, and (something else not given) to form an appropriate recurrence relation. (Do not try to find a closed form).
[Math] How many binary numbers of length n do not contain the substring 000
binarydiscrete mathematicsrecurrence-relations
Best Answer
Ok so I used Akiva's hint and the answers on How many length n binary numbers have no consecutive zeroes ?Why we get a Fibonacci pattern? (close to this but only two and not three $0$'s in a row) and came out with
____$n-3$____$100$
____$n-2$____$10$
____$n-1$____$1$
$n$ being the number of strings that do not contain $000$
and got $Z_n$ = $Z_{n-1}$ + $Z_{n-2}$ + $Z_{n-3}$ which is correct (confirmed by my teacher) for anyone else struggling with this problem