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