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


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}}$.
