# generating function from recurrence relation

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))$.

• I'm having trouble with understanding your expansion of the sum of the recurrence relation with $x^n$. Could you maybe add in a few more intermediate steps, please? Cheers – user141834 Oct 5 '15 at 5:46
• @user141834: For instance, $$\sum_{n=4}^\infty s_{n-1}x^n=x\sum_{n=4}^\infty s_{n-1}x^{n-1}=x\sum_{n=3}^\infty s_nx^n=x(S(x)-1-2x-4x^2)\;.$$ The other terms are treated analogously. – joriki Oct 5 '15 at 5:48
• Also, why is the lower bound of the sum $n=4$? Would it be equivalent to put $n \ge 4$ also? – user141834 Oct 5 '15 at 5:56
• @user141834: People would understand if you write $n\ge4$ instead, people often do, but it's a bit more ambiguous, since it leaves open the upper limit and whether it refers to all integers above $n$ -- the way I wrote it is a bit more explicit. – joriki Oct 5 '15 at 6:33
• Sorry to come back to this question, I'm just reviewing it again. I am having trouble understanding how the $S(x)$ term comes about at the end...I might have just forgotten something trivial but I cant seem to figure that out! – user141834 Nov 7 '15 at 7:10