<s>[INST] 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.
 [/INST] 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.
</s>