Consider ternary strings, that is strings formed from symbols \(0\), \(1\), and \(2\). Let \(Z_n\) be the number of ternary strings of length \(n\) that do not contain substrings \(22\) and \(12\). For example, for \(n=3\), all the strings with this property are: \[\begin{aligned} 000, 001, 002, 010, 011, 020, 021, 100, 101, 102, 110, 111, 200, 201, 202, 210, 211, \end{aligned}\] and thus \(Z_3 = 17\). (Note that \(Z_0 = 1\), because the empty string satisfies the condition.)

(a) Derive a recurrence relation for the numbers \(Z_n\). Justify it.

(b) Find the formula for the numbers \(Z_n\) by solving this recurrence. Show your work.

Solution 1: (a)
\(Z_0 = 1\)
\(Z_1 = 3\) \(\:\{1, 2, 3\}\)
\(Z_2 = 7\) \(\:\{00, 01, 02, 10, 11, 20, 21\}\)
\(Z_3 = 17\)
To compute the recurrence, we can look at the possible endings for the strings.
In the event that the string ends with a \(0\) or \(1\), any other number can precede this instance. Giving us \(2*Z_{n-1}\).
However, if the string ends with \(2\), the number preceding it must be \(0\), since we cannot have the sequence \(12\) or \(22\). This gives us \(Z_{n-2}\)

Graphically this can be represented as:
\(****0 \: \: + \: \: ****1 \: \: + \: \: ***02\)
Where \(*\) represents any number of digits in a string of \(Z\)

Therefore, the recurrence relation is
\(Z_n = 2*Z_{n-1}+Z_{n-2}\)
(b) Finding the characteristic equation, we get:
\(x^2-2x-1=0\)
To find the roots, we use the quadratic equation.
\(\frac{2+\sqrt{4-4(-1)}}{2}\) and \(\frac{2-\sqrt{4-4(-1)}}{2}\)
\(\frac{2+\sqrt{8}}{2}\) and \(\frac{2-\sqrt{8}}{2}\)
\(x = 1+\sqrt{2}\), \(1-\sqrt{2}\)

The general form can be represented as:
\(Z_n = \alpha _1 (1+\sqrt{2})^n + \alpha _2 (1-\sqrt{2})^n\)
Now, we solve for the initial conditions
For \(n=0 \: \: \: \alpha _1 (1+\sqrt{2})^0 + \alpha _2 (1-\sqrt{2})^0 = 1\)
\(\alpha _1 + \alpha _2 = 1\)
\(\alpha _1 = 1 - \alpha _2\)

For \(n=1 \: \: \: \alpha _1 (1+\sqrt{2})^1 + \alpha _2 (1-\sqrt{2})^1 = 3\)
\((1-\alpha _2)(1+\sqrt{2}) + (\alpha _2)(1-\sqrt{2}) = 3\)
\(1-\alpha _2 + \sqrt{2}-\sqrt{2}\alpha _2 + \alpha _2 \ \sqrt{2}\alpha _2 = 3\)
\(1+\sqrt{2}-2\sqrt{2}\alpha _2 = 3\)
\(\sqrt{2}-2\sqrt{2}\alpha _2 = 2\)
\(-2\sqrt{2}\alpha _2 = 2 -\sqrt{2}\)

\(\alpha _2 = \frac{2 -\sqrt{2}}{-2\sqrt{2}}\)
\(\alpha _1 = 1 - \frac{2 -\sqrt{2}}{-2\sqrt{2}}\)

\(Z_n = (1 - \frac{2 -\sqrt{2}}{-2\sqrt{2}})(1+\sqrt{2})^n + (\frac{2 -\sqrt{2}}{-2\sqrt{2}})(1-\sqrt{2})^n\)

Solve the following recurrence equation: \[\begin{aligned} V_n &=& V_{n-1} + 3V_{n-2} + V_{n-3} + 2n\\ V_0 &=& 0 \\ V_1 &=& 0 \\ V_2 &=& 1\end{aligned}\] Show your work (all steps: the associated homogeneous equation, the characteristic polynomial and its roots, the general solution of the homogeneous equation, computing a particular solution, the general solution of the non-homogeneous equation, using the initial conditions to compute the final solution.)

Solution 2:
First, we will find the homogeneous variant
\(x^3-x^2-3x-1 = 0\)
Plugging in a few roots, we find that \(x=-1\) is a root.
Using long division \(\frac{x^3-x^2-3x-1}{x+1}\)
We get a quadratic equation \(x^2-2x-1\)
Then, we solve for the roots of this equation using the quadratic formula and get:
\(x=-1, \: 1+\sqrt{2}, \: 1-\sqrt{2}\)
General solution: \(v^{'}_n = \alpha _1 (-1)^n + \alpha _2 (1+\sqrt{2})^n + \alpha _3 (1-\sqrt{2})^n\)
Particular solution: \(v_n = \alpha _1 (-1)^n + \alpha _2 (1+\sqrt{2})^n + \alpha _3 (1-\sqrt{2})^n + \beta\)

Now, we will solve for \(\beta\)
\(V^{"}_n = \beta _1 n + \beta _2\)
\(\beta _1 n + \beta _2 = (\beta _1(n-1)+\beta _2) + 3(\beta _1(n-2)+\beta _2) + (\beta _1(n-3) + \beta _2) + 2n\)
\(5\beta _1n - 10 \beta _1 + 5 \beta _2 + 2n\)
\((5\beta _2 + 2)n + (5\beta _2 - 10 \beta_1) = 0\)
For \(n = 0\)
\(5\beta _2 - 10 \beta _1 = 0\)
\(\beta _2 = 2\beta _1\)

\(5\beta _1 + 2 + 10\beta _1 - 10\beta _1 = 0\)
\(5\beta _1 = -2\)

\(\beta _1 = -\frac{2}{5}\)
\(\beta _2 = -\frac{4}{5}\)
\(V^{"}_n = -\frac{2}{5}n - \frac{4}{5}\)
General solution: \(v_n = \alpha _1 (-1)^n + \alpha _2 (1+\sqrt{2})^n + \alpha _3 (1-\sqrt{2})^n -\frac{2}{5}n - \frac{4}{5}\)

Initial conditions:
\(n=0\)
\(\alpha _1 = \frac{4}{5}-\alpha _2 - \alpha _3\)
\(n=1\)
\(-\alpha _1 + (1+\sqrt{2})\alpha _2 + (1-\sqrt{2})\alpha _3 = \frac{6}{5}\)
\(n=2\)
\(\alpha _1 + \alpha _2(3+2\sqrt{2})+\alpha _3(3-2\sqrt{2}) = \frac{8}{5}\)
\(\alpha _1 = -\frac{4}{5}-\frac{11}{5\sqrt{2}}-\frac{2-2(\frac{8}{5}+\frac{11}{5\sqrt{2}})+\sqrt{2}(\frac{8}{5}+\frac{11}{5\sqrt{2}})}{2+\sqrt{2}}\)
\(\alpha _2 = \frac{2-2(\frac{8}{5}+\frac{11}{5\sqrt{2}})+\sqrt{2}(\frac{8}{5}+\frac{11}{5\sqrt{2}})}{2+\sqrt{2}}\)
\(\alpha _3 = \frac{8}{5}+\frac{11}{5\sqrt{2}}\)

The solution is:
\(V_n = (-\frac{4}{5}-\frac{11}{5\sqrt{2}}-\frac{2-2(\frac{8}{5}+\frac{11}{5\sqrt{2}})+\sqrt{2}(\frac{8}{5}+\frac{11}{5\sqrt{2}})}{2+\sqrt{2}})(-1)^n+\frac{2-2(\frac{8}{5}+\frac{11}{5\sqrt{2}})+\sqrt{2}(\frac{8}{5}+\frac{11}{5\sqrt{2}})}{2+\sqrt{2}}(1+\sqrt{2})^n+\frac{8}{5}+\frac{11}{5\sqrt{2}}(1-\sqrt{2})^n-\frac{2}{5}n - \frac{4}{5}\)

To submit the homework, you need to upload the pdf file into ilearn by 8AM on Tuesday, May 13, and turn-in a paper copy in class.