bit strings recurrence

Question

Let $f(n)$ denote the number of bit strings. (Words from the alphabet $\{0,1\}$) of length $n$ which do not contain three consecutive zeros. How would you write a linear recurrence of order 3 with adequate initial conditions for $f(n)$. Also need to verify it gives the correct answer for $n = 6$. How would you approach this ?

Answer 1

Hint: Let $b(n)$ be the number of such strings whose last bit is $0$, and $c(n)$ the number whose last two bits are $0$. It's easy to write $f(n+1)$, $b(n+1)$ and $c(n+1)$ in terms of $f(n)$, $b(n)$ and $c(n)$. Then write everything in terms of $f$.

Answer 2

see f(1) = 2, f(2) = 4 and f(3) = 7. from n$\geq$4 onwards, we have to think. Hmm..

f(n-1) might not have any zeros at the end of it, or one zero at the end, or two zeros at the end. Depending on that we can do certain things to each of them and that should give you a recurrence relation.

For example, if f(n-1) has no zeros at the end then we can either append a 0 or 1 at the end and get two times the string given by the f(n-1).

for other two, you can do adjustments accordingly and reach a recurrence involving three terms.