# 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 $t_n$ the number of ternary sequences of length n that do not contain 012:
First, $t_0 = 1$; $t_1 = 3$; and $t_2 = 9$ because ....
To obtain a recursion, let $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 $1 * t_{n-1}$ minus the number of ternary sequences of length $n$ that start 012 but do not have it appearing later in the sequence, which is ... The subtraction is because ... . Hence, for $n \geq 3$; $t_n =$... which, after simplifying,
gives the recurrence $tn = 3*t_{n-1} - t_{n-3}.$

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

2. Originally Posted by Celcius

(b) Find a recurrence relation and initial conditions for $c_n$, the number of sequences of length $n$ of upper case letters that do not contain GOAL.
In order? So, clearly $G,O,A,L,B$ would not be included, but what about $G,O,B,A,L$?

3. Originally Posted by Drexel28
In order? So, clearly $G,O,A,L,B$ would not be included, but what about $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.