Recursive formula for a combinatorial problem and define the generating function Question:

Let $\sigma=\{a,b,c\}$. How many words can we assemble without the substrings $'ab'$ and $'bc'$?

*

*define the recursive formula.

*define the generating function for this formula.



$Solution.A.$
For the first sub-question, we consider 3 disjoint cases: $$a_{n}^{c}=\text{the number of valid words with length of $n$, starting with 'c' }$$
$$a_{n}^{b}=\text{the number of valid words with length of $n$, starting with 'b' }$$
$$a_{n}^{a}=\text{the number of valid words with length of $n$, starting with 'a' }$$
For the first case, we can add $'c'$ at the beginning of the word and then take a valid word with a length of $n-1$. Therefore, we have $a_{n-1}$ options for this case.
For the second case, we use the complement method. We can take all valid words starting with $'b'$ and then get rid of all the options for words with a length of $n-2$ starting with $'c'$. So we have: $a^{b}_{n}=a_{n-1}-a_{n-2}$ options.
For the third case, we use the complement method. We can take all valid words starting with $'a'$ and then get rid of all the options for words with a length of $n-2$ starting with $'b'$. So we have: $$a_{n}^{a} =a_{n-1} -a_{n-1}^{b} =a_{n-1} -( a_{n-2} -a_{n-3}) =a_{n-1} -a_{n-2} +a_{n-3}$$
options.
Now, since all three cases are disjoint then it is clear that: $a_{n} =a_{n}^{a} +a_{n}^{b} +a_{n}^{c}$, so therefore,$$a_{n} =a_{n}^{a} +a_{n}^{b} +a_{n}^{c} =a_{n-1} +a_{n-1} -a_{n-2} +a_{n-1} -a_{n-2} +a_{n-3}\\
=3a_{n-1} -2a_{n-2} +a_{n-3}$$
$Solution.B.$
Let $$F( x) =\sum _{n=0}^{\infty } a_{n} x^{n}$$
Thus,$$  \begin{array}{l}
F( x) =\sum _{n=0}^{\infty } a_{n} x^{n} =a_{0} +a_{1} x+a_{2} x^{2} +\sum _{n=3}^{\infty }( 3a_{n-1} -2a_{n-2} +a_{n-3}) x^{n}\\
\\
=1+3x+7x^{2} +\sum _{n=3}^{\infty }( 3a_{n-1} -2a_{n-2} +a_{n-3}) x^{n}\\
\\
=1+3x+7x^{2} +3\sum _{n=3}^{\infty } a_{n-1} x^{n} -2\sum _{n=3}^{\infty } a_{n-2} x^{n} +\sum _{n=3}^{\infty } a_{n-3} x^{n}\\
\\
=1+3x+7x^{2} +3x\underbrace{\sum _{n=3}^{\infty } a_{n-1} x^{n-1}}_{F( x) \ -\ a_{1} x\ -\ a_{0}} -2x^{2}\underbrace{\sum _{n=3}^{\infty } a_{n-2} x^{n-2}}_{F( x) \ -\ a_{0}} +x^{3}\underbrace{\sum _{n=3}^{\infty } a_{n-3} x^{n-3}}_{F( x)}\\
\\
=1+3x+7x^{2} +3x( F( x) -a_{1} x-a_{0}) -2x^{2}( F( x) -a_{0}) +x^{3} F( x)\\
\\
=1+3x+7x^{2} +3x( F( x) -3x-1) -2x^{2}( F( x) -1) +x^{3} F( x)\\
\\
=1+3x+7x^{2} +3xF( x) -9x^{2} -3x-2x^{2} F( x) +2x^{2} +x^{3} F( x)\\
\\
=1+\left( 3x-2x^{2} +x^{3}\right) F( x)
\end{array}$$
therefore, we have that: $$ \begin{array}{l}
F( x) =1+\left( 3x-2x^{2} +x^{3}\right) F( x) /-\left( 3x-2x^{2} +x^{3}\right) F( x)\\
\\
F( x) -\left( 3x-2x^{2} +x^{3}\right) F( x) =1\\
\\
\left( 1-\left( 3x-2x^{2} +x^{3}\right)\right) F( x) =1\\
\\
\left( 1-3x+2x^{2} -x^{3}\right) F( x) =1/:\left( 1-3x+2x^{2} -x^{3}\right)\\
\\
\boxed{F( x) =\frac{1}{1-3x+2x^{2} -x^{3}}}
\end{array}$$

Now, is it correct?
 A: The following answer is based upon the Goulden-Jackson Cluster Method. We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{\sigma}=\{a,b,c\}$$ and the set $B=\{ab,bc\}$ of bad words, which are not allowed to be part of the words we are looking for. We derive a generating function $F(x)$ with the coefficient of $x^n$ being  the number of wanted words of length $n$.
According to the paper (p.7) the generating function $F(x)$  is
\begin{align*}
F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\tag{1}
\end{align*}
with $d=|\mathcal{V}|=3$, the size of the alphabet and $\mathcal{C}$ is the weight-numerator of bad words with
\begin{align*}
\text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[ab])+\text{weight}(\mathcal{C}[bc])\tag{2}
\end{align*}
We calculate according to the paper
\begin{align*}
\text{weight}(\mathcal{C}[bc])&=-x^2\\
\text{weight}(\mathcal{C}[ab])&=-x^2-x\cdot\text{weight}(\mathcal{C}[bc])\tag{3}\\
\end{align*}
so  that
\begin{align*}
\text{weight}(\mathcal{C})=-x^2+\left(-x^2-x\cdot\left(-x^2\right)\right)=-2x^2+x^3
\end{align*}
The additional term on the right-hand side of (3) takes account of the overlapping of $\color{blue}{b}c$ with $a\color{blue}{b}$.

We obtain according to (1) and (3)
\begin{align*}
\color{blue}{F(x)}&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\
&\; \color{blue}{=\frac{1}{1-3x+2x^2-x^3}}\\
&=1+3x+7x^2+16x^3+\color{blue}{37}x^4+86x^5\\
&\qquad+200x^6+465x^7+1\,081x^8+\cdots
\end{align*}
in accordance with OPs result.

The last line was calculated with some help of Wolfram Alpha. The blue marked coefficient of $x^4$ tells us that out of $3^4=81$ words of length $4$ there are $37$ valid words which do not contain $ab$ or $bc$. These $37$ words are listed below.
\begin{align*}
\begin{array}{cccccc}
\text{aaaa}&\text{aaac}&\text{aaca}&\text{aacb}&\text{aacc}&\text{acaa}\\
\text{acac}&\text{acba}&\text{acbb}&\text{acca}&\text{accb}&\text{accc}\\
\text{baaa}&\text{baac}&\text{baca}&\text{bacb}&\text{bacc}&\text{bbaa}\\
\text{bbac}&\text{bbba}&\text{bbbb}&\text{caaa}&\text{caac}&\text{caca}\\
\text{cacb}&\text{cacc}&\text{cbaa}&\text{cbac}&\text{cbba}&\text{cbbb}\\
\text{ccaa}&\text{ccac}&\text{ccba}&\text{ccbb}&\text{ccca}&\text{cccb}\\
\text{cccc}
\end{array}
\end{align*}
