I've been trying this for a long time. An example is:
N = 5.
Then we can have 11011 which is only one substring.
But if N = 9,
We can have many binary strings in the form
11011xxxx 2^4 combinations
x11011xxx 2^4 combinations
xx11011xx 2^4 combinations
xxx11011x 2^4 combinations
xxxx11011 2^4 combinations
But this is the case of overcounting. (110110110) is one string, but is counted as 2.
How do we avoid this?
Note: this question came in the 2016 ZIO.
Best Answer
Here we are looking for binary strings of length $N$ which do not contain the substring $11011$. The result is then $2^N$ minus this number.
It follows: A generating function $F(x)$ for the number of words built from $\{0,1\}$ which do not contain the subword $11011$ is \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-2x+\frac{x^5}{1+x^3+x^4}}\\ &=\frac{1+x^3+x^4}{1-2x+x^3-x^4-x^5} \end{align*}
Since the generating function counting the number $2^N$ of all binary strings of length $N$ is \begin{align*} \frac{1}{1-2x}=1+2x+4x^2+\cdots \end{align*}
For example the $12$ strings of length $7$ containing the substring $11011$ are
\begin{array}{cccc} \color{blue}{00}11011\quad&\quad\color{blue}{0}11011\color{blue}{0}\quad&\quad11011\color{blue}{00}\\ \color{blue}{01}11011\quad&\quad\color{blue}{0}11011\color{blue}{1}\quad&\quad11011\color{blue}{01}\\ \color{blue}{10}11011\quad&\quad\color{blue}{1}11011\color{blue}{0}\quad&\quad11011\color{blue}{10}\\ \color{blue}{11}11011\quad&\quad\color{blue}{1}11011\color{blue}{1}\quad&\quad11011\color{blue}{11}\\ \end{array}