Find the generating function for this set of strings Let $a(n)$ be the number of $\{0,1\}$-strings of length $n$ which contain no $4$ consecutive $1$'s and no $4$ consecutive $0$'s (don't contain "$0000$" or "$1111$"). Find the generating function for this.
Thank you.
 A: Let $A_n$ be the number of ways to write $n$ with your conditions.
Hint: By considering the initial string of similar digits, show that $A_n = A_{n-1} + A_{n-2} + A_{n-3}$.
Use the initial conditions that $A_1 = 2, A_2 = 4, A_3 = 8 $.
A: Let $a(n)$ denote the number of admissible binary strings of length $n$. First, note that precisely half of the strings of any length end in $\color{red}{0}$ (or $\color{green}{1}$). Now, for a string of length $n>4$, there are $8$ possible endings with the following numbers of occurrences:
$$\begin{align*}
&\overbrace{\ldots???\color{green}{1}}^{\text{length }n-3}\color{red}{0}\color{red}{0}\color{red}{0}\quad\tfrac{1}{2}a(n-3)\\\
&\ldots????\color{red}{0}\color{red}{0}\color{green}{1}\quad\tfrac{1}{2}a(n-4)+\tfrac{1}{2}a(n-3)\\
&\ldots????\color{red}{0}\color{green}{1}\color{red}{0}\quad\tfrac{1}{2}a(n-2)\\
&\ldots????\color{red}{0}\color{green}{1}\color{green}{1}\quad\tfrac{1}{2}a(n-2)\\
&\ldots????\color{green}{1}\color{red}{0}\color{red}{0}\quad\tfrac{1}{2}a(n-2)\\
&\ldots????\color{green}{1}\color{red}{0}\color{green}{1}\quad\tfrac{1}{2}a(n-2)\\
&\ldots????\color{green}{1}\color{green}{1}\color{red}{0}\quad\tfrac{1}{2}a(n-4)+\tfrac{1}{2}a(n-3)\\
&\underbrace{\ldots???\color{red}{0}}_{\text{length }n-3}\color{green}{1}\color{green}{1}\color{green}{1}\quad\tfrac{1}{2}a(n-3)
\end{align*}$$
Summing up, we obtain the following recursion formula:
$$a(n)=2a(n-2)+2a(n-3)+a(n-4)$$
Finally, we determine $a(n)$ from the initial values
$$a(1)=2, a(2)=4, a(3)=8, a(4)=14.$$
Reassuring note:
Substituting $a(n-1)=a(n-2)+a(n-3)+a(n-4)$ in $\textbf{Calvin Lin}$'s recurrence relation $a(n)=a(n-1)+a(n-2)+a(n-3)$, we obtain agreement.
A: Such a string consists of a (possibly empty) sequence of elements from {01, 011, 0111, 001, 0011, 00111, 0001, 00011, 000111} — i.e. {0|00|000}{1|11|111} — optionally preceded by 1, 11 or 111 and optionally followed by 0, 00 or 000. So the generating function is
$$
\frac{(1+z+z^2+z^3)^2}{1-(z+z^2+z^3)^2},
$$ 
the numerator reflecting the optional prefix and suffix, and the denominator reflecting the sequence.
This is a related question.
