Consider ternary strings, that is strings formed from symbols 0, 1, and 2. Let Zn 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: 000, 001, 002, 010, 011, 020, 021, 100, 101, 102, 110, 111, 200, 201, 202, 210, 211, and thus Z₃ = 17. (Note that Z₀ = 1, because the empty string satisfies the condition.) (a) Derive a recurrence relation for the numbers Zn. Justify it. (b) Find the formula for the numbers Zn by solving this recurrence. Show your work. SOLUTION 1: (a) Z₀ = 1 Z₁ = 3 {1, 2, 3} Z₂ = 7 {00, 01, 02, 10, 11, 20, 21} Z₃ = 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 * Zn − 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 Zn − 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 Zn = 2 * Zn − 1 + Zn − 2 (b) Finding the characteristic equation, we get: x² − 2x − 1 = 0 To find the roots, we use the quadratic equation. $}{2}$ and $}{2}$ $}{2}$ and $}{2}$ $x = 1+$, $1-$ The general form can be represented as: $Z_n = \alpha _1 (1+)^n + \alpha _2 (1-)^n$ Now, we solve for the initial conditions For $n=0 \: \: \: \alpha _1 (1+)^0 + \alpha _2 (1-)^0 = 1$ α₁ + α₂ = 1 α₁ = 1 − α₂ For $n=1 \: \: \: \alpha _1 (1+)^1 + \alpha _2 (1-)^1 = 3$ $(1-\alpha _2)(1+) + (\alpha _2)(1-) = 3$ $1-\alpha _2 + -\alpha _2 + \alpha _2 \ \alpha _2 = 3$ $1+-2\alpha _2 = 3$ $-2\alpha _2 = 2$ $-2\alpha _2 = 2 -$ $\alpha _2 = }{-2}$ $\alpha _1 = 1 - }{-2}$ $Z_n = (1 - }{-2})(1+)^n + (}{-2})(1-)^n$ Solve the following recurrence equation: V_n &=& V_{n-1} + 3V_{n-2} + V_{n-3} + 2n\\ V_0 &=& 0 \\ V_1 &=& 0 \\ V_2 &=& 1 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³ − x² − 3x − 1 = 0 Plugging in a few roots, we find that x = −1 is a root. Using long division ${x+1}$ We get a quadratic equation x² − 2x − 1 Then, we solve for the roots of this equation using the quadratic formula and get: $x=-1, \: 1+, \: 1-$ General solution: $v^{'}_n = \alpha _1 (-1)^n + \alpha _2 (1+)^n + \alpha _3 (1-)^n$ Particular solution: $v_n = \alpha _1 (-1)^n + \alpha _2 (1+)^n + \alpha _3 (1-)^n + \beta$ Now, we will solve for β $V^{"}_n = \beta _1 n + \beta _2$ β₁n + β₂ = (β₁(n − 1)+β₂)+3(β₁(n − 2)+β₂)+(β₁(n − 3)+β₂)+2n 5β₁n − 10β₁ + 5β₂ + 2n (5β₂ + 2)n + (5β₂ − 10β₁)=0 For n = 0 5β₂ − 10β₁ = 0 β₂ = 2β₁ 5β₁ + 2 + 10β₁ − 10β₁ = 0 5β₁ = −2 $\beta _1 = -{5}$ $\beta _2 = -{5}$ $V^{"}_n = -{5}n - {5}$ General solution: $v_n = \alpha _1 (-1)^n + \alpha _2 (1+)^n + \alpha _3 (1-)^n -{5}n - {5}$ Initial conditions: n = 0 $\alpha _1 = {5}-\alpha _2 - \alpha _3$ n = 1 $-\alpha _1 + (1+)\alpha _2 + (1-)\alpha _3 = {5}$ n = 2 $\alpha _1 + \alpha _2(3+2)+\alpha _3(3-2) = {5}$ $\alpha _1 = -{5}-{5}-{5}+{5})+({5}+{5})}{2+}$ $\alpha _2 = {5}+{5})+({5}+{5})}{2+}$ $\alpha _3 = {5}+{5}$ The solution is: $V_n = (-{5}-{5}-{5}+{5})+({5}+{5})}{2+})(-1)^n+{5}+{5})+({5}+{5})}{2+}(1+)^n+{5}+{5}(1-)^n-{5}n - {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.