I am referring to another question of mine: recurrence relation of a language
However, in this question, I am considering the language X of bitstrings with no more than 3 consecutive zeros. (original question considered no more than 2)
I have come up with the following recurrence relation for the sequence $s_n$ which is the number of words in $X$ with length $n$:
$s_n=s_{n-1}+s_{n-2}+s_{n-3} + s_{n-4}$
My attempt at finding a generating function is as follows:
$S(x) = s_0 + s_1x + s_2x^2 + s_3x^3 + \sum_{n \ge 4} s_nx^n$ where $s_0 = 1, s_1 = 2, s_2 = 4,$ and $s_3 = 8$
However, I am not sure how to proceed from here.
Sum the recursion relation with $x^n$ to obtain
\begin{align} 0&=\sum_{n=4}^\infty(s_n-s_{n-1}-s_{n-2}-s_{n-3}-s_{n-4})x^n\\ &=S(x)-1-2x-4x^2-8x^3-x(S(x)-1-2x-4x^2)-x^2(S(x)-1-2x)-x^3(S(x)-1)-x^4S(x) \end{align}
and thus
$$ S(x)(1-x-x^2-x^3-x^4)=1+x+x^2+x^3\;,\\ S(x)=\frac{1+x+x^2+x^3}{1-x-x^2-x^3-x^4}\;. $$
Another way to arrive at this generating function is to note that you can have up three zeros, accounting for the factor $1+x+x^2+x^3$, and then any number of blocks with a one followed by up to three zeros; each block is described by $f(x)=x+x^2+x^3+x^4$, and having any number of them yields $1/(1-f(x))$.