ROUGH DRAFT authorea.com/7070
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • 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.

    [Someone else is editing this]