CS111 Homework Assignment 3

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.