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?

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$
