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."
  

 A: If we have such a string of length $n$, there are two possibilities.  First, it could end in either $0$ or $1$, in which case after removing the last digit we have any such string of length $n-1$.  Second, it could end in $2$.  Then, the next-to-last digit cannot be $2$.  It could be either $0$ or $1$, and is preceded by one of these strings of length $n-2$.  Therefore, if $a_n$ counts how many of these strings there are of length $n$, then this sequence satisfies the recurrence $a_n=2a_{n-1}+2a_{n-2}$ (for $n\ge 3$, and in fact also for $n=2$).  The initial conditions are $a_0=1, a_1=3, a_2=8$.  
Edit: fixed silly typo
A: You can uniquely generate the set of strings using $(0|1|20|21)^∗(2|ϵ)$, hence your generating function is $\frac{1}{1 - (x + x + x^2 + x^2)} \cdot (1 + x) = \frac{1 + x}{1 - 2(x + x^2)}$.
Let $\frac{1 + x}{1 - 2(x + x^2)} = a_0 + a_1x + a_2x^2 + \cdots$. Then by multiplying both sides by $1 - 2(x + x^2)$ and looking at the terms with the appropriate powers, we get $1 = 1a_0$ so $a_0 = 1$; $1 = 1a_1 - 2a_0 = 1a_1 - 2$ so $a_1 = 3$; and for $n \geq 2$, $0 = 1a_n - 2a_{n - 1} - 2a_{n - 2}$, so $a_n = 2a_{n - 1} + 2a_{n - 2}$. Note this checks out since there is one such string of length 0 (the empty string), and 3 such strings of length 1. You can also check that $a_2 = 2a_1 + 2a_0 = 8$ checks out since there are 8 such strings of length 2.
Since you have the linear recurrence $a_{n + 2} - 2a_{n + 1} - 2a_n = 0$, you have to look at the roots of $x^2 + x + 2$, which are $1 + \sqrt{3}$ and $1 - \sqrt{3}$. Hence $a_n = A(1 + \sqrt{3})^n + B(1 - \sqrt{3})^n$ for some constants $A$ and $B$. By plugging in $n = 0$ and $n = 1$ you can solve $A = \frac{\sqrt{3} + 2}{2\sqrt{3}}$ and $B=\frac{\sqrt{3} - 2}{2\sqrt{3}}$, hence $a_n = \frac{(\sqrt{3} + 2)(1 + \sqrt{3})^n + (\sqrt{3} - 2)(1 - \sqrt{3})^n}{2\sqrt{3}}$.
A: 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.
