# Thread: Recurrence of a Ternary Sequence

1. ## Recurrence of a Ternary Sequence

(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.

2. Originally Posted by Celcius

(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.
In order? So, clearly $\displaystyle G,O,A,L,B$ would not be included, but what about $\displaystyle G,O,B,A,L$?

3. Originally Posted by Drexel28
In order? So, clearly $\displaystyle G,O,A,L,B$ would not be included, but what about $\displaystyle G,O,B,A,L$?
Thanks for your response. From my understanding, G O B A L is allowed. The letters must be in order and together.