(a) A ternary sequence is one in which each element is 0, 1, or 2. Complete the following argument to find a recurrence relation and initial

conditions for $\displaystyle t_n$ the number of ternary sequences of length n that do not contain 012:

First, $\displaystyle t_0 = 1$; $\displaystyle t_1 = 3$; and $\displaystyle t_2 = 9$ because ....

To obtain a recursion, let $\displaystyle n \geq 3$ and focus on the first element of the sequence. There are two cases depending on whether it equals zero.

If the first element is not zero, then ...

If the first element is zero then the number of sequences without 012 equals $\displaystyle 1 * t_{n-1}$ minus the number of ternary sequences of length $\displaystyle n$ that start 012 but do not have it appearing later in the sequence, which is ... The subtraction is because ... . Hence, for $\displaystyle n \geq 3$; $\displaystyle t_n =$... which, after simplifying,

gives the recurrence $\displaystyle tn = 3*t_{n-1} - t_{n-3}.$

(b) Find a recurrence relation and initial conditions for $\displaystyle c_n$, the number of sequences of length $\displaystyle n$ of upper case letters that do not contain GOAL.