How to express this bitstring sequence as an OGF? I am wondering how we can express this sequence $B_{101}$ as an ordinary generating function (OGF), where $B_{101}$ is defined as the set of bitstrings (i.e. strings formed from $0$ and $1$) that does not have $101$ as a substring.
For instance, for the bitstring $B_{00}$, which is defined as the set of bitstrings that do not have the substring $00$, we can have a generating function $G(z)$, where:
$$
G(z) =  1 + z + (z+z^2)G(z)
$$
In this case, $G(z)=a_0z^0 + a_1z^1 + a_2z^2 + ...$, and the coefficient $a_k$ of $z^k$ gives the number of bitstrings of length $k$ that do not have the substring $00$...
 A: The first few terms are $1,2,4,7,12,21$; I looked this up in OEIS, and the first return was OEIS $A005251$, $$\langle a_n:n\ge 0\rangle=\langle 0,1,1,1,2,4,7,12,21,\ldots\rangle\;,$$ of which we are told that $a_{n+3}$ is the number of $n$-bit sequences that avoid $010$. Thus, you want
$$G(z)=\sum_{n\ge 0}a_{n+3}z^n\;,$$
where
$$\sum_{n\ge 0}a_nz^n=\frac{z(1-z)}{1-2z+z^2-z^3}\;,$$
according to the OEIS entry. This generating function can be derived from the recurrence $a_n=2a_{n-1}-a_{n-2}+a_{n-3}$, with initial conditions $a_0=0$ and $a_1=a_2=1$. The recurrence isn’t hard to justify.
Here a sketch of how you could do it from scratch, without relying on OEIS. Say that a bit string is good if it avoids $101$, and let $b_n$ be the number of good $n$-bit strings; we’ll begin by finding a recurrence for $b_n$. As a first approximation, each good $(n-1)$-bit string $\sigma$ can be extended to two $n$-bit strings, $\sigma^\frown 0$ and $\sigma^\frown 1$; $\sigma^\frown 0$ is definitely good, and $\sigma^\frown 1$ is good unless $\sigma$ ends in $10$. Thus, $b_n$ is $2b_{n-1}$ minus the number of good $(n-1)$-bit strings that end in $10$.
Every good $(n-1)$-bit string that ends in $0$ is obtained by appending a $0$ to a good $(n-2)$-bit string, and every good $(n-2)$-bit string can be extended to a good $(n-1)$-bit string ending in $0$, so there are $b_{n-2}$ good $(n-1)$-bit strings that end in $0$. A similar argument shows that $b_{n-3}$ of them end in $00$, so $b_{n-2}-b_{n-3}$ of them end in $10$, and it follows that
$$b_n=2b_{n-1}-(b_{n-2}-b_{n-3})=2b_{n-1}-b_{n-2}+b_{n-3}\;.$$
One can now use this recurrence to derive the generating function in the usual way.
A: This answer is based upon the Goulden-Jackson Cluster Method.

We consider the set words of length $n\geq 0$ built from an alphabet $\mathcal{V}=\{0,1\}$ and the set $B=\{101\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $G(z)$ with the coefficient of $z^n$ being  the number of valid  words of length $n$.

According to the paper (p.7) the generating function $G(z)$  is
\begin{align*}
G(z)=\frac{1}{1-dz-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{V}|=2$, the size of the alphabet and $\mathcal{C}$ the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[101])
\end{align*}

We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[101])&=-z^3-\text{weight}(\mathcal{C}[101])z^2\tag{2}\\
\end{align*}
It    follows  from  (1)  and (2)
\begin{align*}
\color{blue}{G(z)}&\color{blue}{=\frac{1}{1-2z+\frac{z^3}{1+z^2}}}\\
&=\frac{1+z^2}{1-2z+z^2-z^3}\\
&=1 + 2 z + 4 z^2 + 7 z^3 + 12 z^4\\
&\qquad+ \color{blue}{21} z^5 + 37 z^6 + 65 z^7 + 114 z^8 \cdots
\end{align*}

The last line was calculated with the help of Wolfram Alpha.  The coefficient   of $z^5$ for example shows there are $\color{blue}{21}$ valid words of  length $5$ from the alphabet $\{0,1\}$ which do not contain the word $101$. The $2^5-21=11$ invalid words are
\begin{align*}
&\color{blue}{101}00\qquad 0\color{blue}{101}0\qquad 00\color{blue}{101}\\
&\color{blue}{101}01\qquad 0\color{blue}{101}1\qquad 01\color{blue}{101}\\
&\color{blue}{101}10\qquad 1\color{blue}{101}0\qquad \\
&\color{blue}{101}11\qquad 1\color{blue}{101}1\qquad 11\color{blue}{101}\\
\end{align*}
