How many length-$n$ bitstrings containing $3$ consecutive $0$s and $4$ consecutive $1$s are there? 
How many length-$n$ bitstrings containing $3$ consecutive $0$s and $4$ consecutive $1$s are there?


I thought that $a_n$ can be constructed in three ways:

*

*The strings that contain both three consecutive $0s$ and four consecutive $1s$ and end up with a $0$. Hence, there are $a_{n-1}$ such  strings.


*The strings that contain both three consecutive $0s$ and four consecutive $1s$ and end up with a $1$. Hence , there are $a_{n-1}$ such  strings.


*The strings that end up with $\dots1111000$ or $\dots0001111$ . There are $2 \times 2^{n-7} = 2^{n-6}$ such strings.
As a result ,the number of length-$n$ strings that contain both three consecutive $0s$ and four consecutive $1s$ is equal to $$a_n = 2a_{n-1}+2^{n-6}$$ with $a_0, a_1,\dots, a_6 =0$ and $a_7 = 2$.  Is this correct? If not, can you write correct closed formula?
 A: Well , first of all we should think about basic set theory . We know that all situations consist of $4$ subcases such that ( containing $3$ consecutive zeros and $4$ consecutive ones ) $\color{red}{\cup}$ ( containing $3$ consecutive zeros and do not contain $4$ consecutive ones ) $\color{red}{\cup}$ (do not contain $3$ consecutive zeros and contain $4$ consecutive ones ) $\color{red}{\cup}$ (do not contain $3$ consecutive zeros and do not contain $4$ consecutive ones ) $\color{blue}{=}$ All situations ,i.e , $2^n$ where $n$ is lenght of the string.
Then , lets call our situations such that
$x_1=$ The number of strings that containing $3$ consecutive zeros and $4$ consecutive ones
$x_2=$ The number of strings that containing $3$ consecutive zeros and do not contain $4$ consecutive ones
$x_3=$ The number of strins that do not contain $3$ consecutive zeros and contain $4$ consecutive ones
$x_4 =$ The number of strings that do not contain $3$ consecutive zeros and do not contain $4$ consecutive ones
We said that $x_1 + x_2 + x_3 + x_4 = 2^n$  ,and we are looking for $x_1$ . If we think these like set operations  , it is clear that $x_1 = 2^n - [x_2 +x_3 -x_4]$.
Moreover , $x_2 + x_4 =$ the number of strings that do not contain $4$ consecutive $1's$ , $x_3+x_4 =$ the number of strings that do not contain $3$ consecutive $0's$.
Result , $x_2 + x_3 -x_4 =$ (the number of strings that do not contain $4$ consecutive $1's$ ) + ( the number of strings that do not contain $3$ consecutive $0's$) - (The number of strings that do not contain $3$ consecutive zeros and do not contain $4$ consecutive ones)
The rest is the process of finding generating functions for them by  Goulden -jackson . I am not get in elaborately that process , you can find explanation on the stack -exchange about it.
So ,
the generating function for the number of strings that do not contain $4$ consecutive $1's$  : $$\frac{1-x^4}{1-2x+x^5}$$
the generating function for the number of strings that do not contain $3$ consecutive $0's$ : $$\frac{1-x^3}{1-2x+x^4}$$
The generating functions for the number of strings that do not contain $3$ consecutive zeros and do not contain $4$ consecutive ones : $$\frac{1+2x +3x^2 +3x^3 +2x^4 +x^5}{1-x^2 -2x^3 -2x^4 -x^5}$$
The generating function for $2^n$ is $$\frac{1}{1-2x}$$
Then , $$x_1 = \frac{1}{1-2x} - \Biggl[\frac{1-x^4}{1-2x+x^5} + \frac{1-x^3}{1-2x+x^4} - \frac{1+2x +3x^2 +3x^3 +2x^4 +x^5}{1-x^2 -2x^3 -2x^4 -x^5} \Bigg] $$
Hence , $$x_1 = 2x^7 +8x^8 + \color{blue}{26}x^9 +75x^{10}+...$$
$26x^9$ means that there are $26$ string of lenght $9$ that contain $000$ and $1111$
A: Here's a recursive approach that might be useful.
Let $b_n$ be the number of length-$n$ bit strings that contain 3 consecutive 0s.  By conditioning on the prefix 1, 01, 001, or 000, we find that
$$b_n = 
\begin{cases}
0 &\text{if $n < 3$} \\
b_{n-1} + b_{n-2} + b_{n-3} + 2^{n-3} &\text{if $n \ge 3$}
\end{cases}
$$
Note that $b_n$ is https://oeis.org/A050231.
Similarly, let $c_n$ be the number of length-$n$ bit strings that contain 4 consecutive 1s.  By conditioning on the prefix 0, 10, 110, 1110, or 1111, we find that
$$c_n = 
\begin{cases}
0 &\text{if $n < 4$} \\
c_{n-1} + c_{n-2} + c_{n-3} + c_{n-4} + 2^{n-4} &\text{if $n \ge 4$}
\end{cases}
$$
Note that $c_n$ is https://oeis.org/A050232.
Now let $a^0_n,a^{00}_n,a^1_n,a^{11}_n,a^{111}_n$ be the number of length-$n$ bit strings that contain 3 consecutive 0s and 4 consecutive 1s and start with 0, 00, 1, 11, and 111, respectively.  Then conditioning on whether the next bit is 0 or 1 yields
\begin{align}
a_n &= a^0_n + a^1_n \\
a^0_n &= a^{00}_n + a^1_{n-1} \\
a^{00}_n &= c_{n-3} + a^1_{n-2} \\
a^1_n &= a^0_{n-1} + a^{11}_n \\
a^{11}_n &= a^0_{n-2} + a^{111}_n \\
a^{111}_n &= a^0_{n-3} + b_{n-4}
\end{align}
