Write a linear recurrence of order $3$ Let $f(n)$ denote the number of bitstrings (words from the alphabet {$0, 1$}) of length $n$ which do not contain three consecutive zeros. Write a linear recurrence of order $3$ with adequate initial conditions for $f(n)$. Verify that it gives the correct answer for $n = 6$.

Can anyone show me how to solve this question? I'm really struggling on this question
 A: I'm not sure whether generating functions might be too advanced for the OP, but I thought I'd show how that would answer the question...
So, first consider the generating function for sequences which are either empty, or begin with a 0 and end with a 1.  Such a sequence is a repetition of 0 of more blocks, each consisting of 1 or 2 0's followed by 1 or more 1's.  So, the generating function for 0 blocks is 1; the generating function for 1 block is $(x+x^2) \cdot (x + x^2 + x^3 + \cdots) = (x+x^2) \cdot \frac{x}{1-x}$; the generating function for 2 blocks is the square of that; and so on.  So, the overall generating function is
$$ \sum_{k=0}^\infty \left[(x+x^2) \cdot \frac{x}{1-x}\right]^k = \frac{1}{1 - (x+x^2) \cdot \frac{x}{1-x}} = \frac{1-x}{1 - x - x^2 - x^3}. $$
Now, to add the possibility of starting with some 1's and ending with some 0's, 0 or more 1's at the start multiplies the generating function by $1 + x + x^2 + x^3 + \cdots = \frac{1}{1-x}$; and adding 0, 1, or 2 0's at the end multiplies the generating function by $1 + x + x^2$.  Therefore, the final generating function is
$$ \sum_{k=0}^\infty f(k) x^k = \frac{1 + x + x^2}{1 - x - x^2 - x^3}. $$
From this, you can almost directly read from the denominator a recurrence relation of:
$$ f(n) = f(n-1) + f(n-2) + f(n-3). $$
A: Let $f(n)$
be the number of strings
of length $n$.
Consider the number of zeros
at the end of the string
of length $n$.
Consider the last two digits.
If they are
11 or 01,
the string of length n+1
can end with a zero or 1.
If they are 10
the string of length n+1
can again end with a zero or 1.
If they are 00,
the string of length n+1
can only end with a 1.
Does this help?
You may want to consider
$f_{ij}(n)$
to be the number of strings
of length $n$
that end in
$ij$,
where
$ij = 00, 01, 10, 11$
and get recurrences for each.
