<s>[INST] Strings and Substrings So here is one of the last homeworks we are doing in my Discrete math class. It seems like it should be simple but I am really stuck. Any help would be greatly appreciated. 

  
*
  
*Find the ordinary generating series with respect to length
  for the strings in $\{0,1,2\}^*$ having no "$22$" substring.  
  
*Find a recurrence satisfied by the coefficients of the generating
  series.
  
*Find an explicit formula for the number of such  strings of length n,
  where n is a non-negative integer."
  

 [/INST] A general way to solve such problems is to set up a system of recurrences. Call $a_n$, $b_n$ and $c_n$ the number of strings of length $n$ of interest that end in 0, 1, 2 respectively. Then:
$$
\begin{align*}
a_{n + 1} &= a_n + b_n + c_n \\
b_{n + 1} &= a_n + b_n + c_n \\
c_{n + 1} &= a_n + b_n
\end{align*}
$$
It is also $a_1 = b_1 = c_1 = 1$. We are interested in $s_n = a_n + b_n + c_n$,
which coincidentally is just $a_{n + 1}$.
Define ordinary generating functions:
$A(z) = \sum_{n \ge 0} a_{n + 1} z^n$ and similarly $B(z)$, $C(z)$. By properties of ordinary generating functions:
$$
\begin{align*}
\frac{A(z) - a_1}{z} &= A(z) + B(z) + C(z) \\
\frac{B(z) - a_1}{z} &= A(z) + B(z) + C(z) \\
\frac{C(z) - a_1}{z} &= A(z) + B(z)
\end{align*}
$$
The solution to this linear system of equations is:
$$
\begin{align*}
A(z) &= \frac{1 + z}{1 - 2 z - 2 z^2} \\
B(Z) &= \frac{1 + z}{1 - 2 z - 2 x^2} \\
C(z) &= \frac{1}{1 - 2 z - 2 z^2}
\end{align*}
$$
We are interested in $a_{n +1}$. Spliting the expresison for $A(z)$ into partial fractions:
$$
A(z) = - \frac{2 - \sqrt{3}}{2 \sqrt{3}} \cdot \frac{1}{1 - (1 - \sqrt{3}) z}
         + \frac{2 + \sqrt{3}}{2 \sqrt{3}} \cdot \frac{1}{1 - (1 + \sqrt{3}) z}
$$
Two geometric series.
</s>