0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user141834 Oct 5 '15 at 5:46
  • 1
    $\begingroup$ @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. $\endgroup$ – joriki Oct 5 '15 at 5:48
  • $\begingroup$ Also, why is the lower bound of the sum $n=4$? Would it be equivalent to put $n \ge 4$ also? $\endgroup$ – user141834 Oct 5 '15 at 5:56
  • $\begingroup$ @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. $\endgroup$ – joriki Oct 5 '15 at 6:33
  • $\begingroup$ 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! $\endgroup$ – user141834 Nov 7 '15 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.