Generating series for ternary strings without 000 and not ending with 0 I would like to find a formula for $T_n$, the number of ternary strings of length $n$ so that they do not contain three consecutive zeroes, and they do not end with $0$ as well. I can find a recurrence relation for $T_n$, however I wonder if we can express $T_n$ as a coefficient of a generating series. Thanks for any help!
 A: I see that you work over recurrence relations , and you are willing to learn. Hence , i will share a very powerful method with you. You can handle nearly all recurrence relation problems with it. Our method is Goulden -Jackson- Cluster Method . I put that link for you , you can read it to learn detaily.
Lets turn to our question. We can claim that $\color{red}{|}$the number of strings that do not have three consecutive zeros$\color{red}{|}$ = $\color{blue}{|}$ the number of strings that do not have three consecutive zeros and end up with $0$$\color{blue}{|}$ + $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $1$ $\color{red}{|}$ + $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $2$ $\color{red}{|}$.
Here , we are looking for $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $1$ $\color{red}{|}$ + $\color{red}{|}$ the number of strings that do not have three consecutive zeros and end up with $2$ $\color{red}{|}$. Right ?
We can see that the number of strings of length $n$ that do not have three consecutive zeros and end up with $1$ is equal to the number of strings of length $(n-1)$ that do not have three consecutive zeros. It is also valid for the string that ends up with $2$.
Now , it is the time for using our powerful method. We will find a generating function and convert it into a sequence of length $(n-1)$.
Lets first calculate for the string end up with $1$ and do not have $3$ consecutive zeros.We said that it is equal to the number of string of length $n-1$ that does not have three consecutive zeros.
We know that our alphabet consists of $3$ elements such as $V=\{0,1,2\}$ , and our bad word is $\{000\}$.
According to the paper $(p.7)$ the generating function $A(z)$ is $$A(z)=\frac{1}{1-dz - \text{weight}(c)}$$
with $d=|V|=3$, the size of the alphabet and $C$ the weight-numerator of bad words with $$\text{weight(c)}= \text{weight}([000])$$
$$\text{weight}([000])= -z^3 - (z^2 +z)\text{weight}([000])$$
$$\text{A(z)}= \frac{1}{1-3z + \frac{z^3}{1+z+z^2}}$$
$$\text{A(z)}= \frac{1+z+z^2}{1-2z-2z^2 -2z^3}$$
We also obtain the same result for the string end up with $2$. Then , the sum of them will give us the generating function for them.Namely , $$\frac{2+2z+2z^2}{1-2z-2z^2 -2z^3}$$
Now , we should convert it into recurrence relation by We recall if a generating function has a representation as rational function of the form
\begin{align*}
A(z)=\sum_{n=0}^\infty a_n z^n=\frac{P(z)}{Q(z)}
\end{align*}
with $P(z), Q(z)$ polynomials, $\deg Q=q>\deg P$ and
\begin{align*}
Q(z)=1+\alpha_1 z+\alpha_2 z^2+\cdots + \alpha_q z^q
\end{align*} then the coefficients $a_n$ follow the recurrence relation
\begin{align*}
a_{n+q}+\alpha_1 a_{n+q-1}+\alpha_2 a_{n+q-2}+\cdots +\alpha_q a_{n}=0\qquad\qquad n\geq 0
\end{align*}
Then , our recurrence relation is $$a_{n-1}=2a_{n-2}+2a_{n-3}+2a_{n-4}$$
Calculation via wolfram
It means that for $n=4$ , there are $52$ such strings , for $n=5$ , there are $152$ such strings , for $n=15$ , the answer is $6843168$ ,so on..
