(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 the number of ternary sequences of length n that do not contain 012:
First, ; ; and because ....
To obtain a recursion, let 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 minus the number of ternary sequences of length that start 012 but do not have it appearing later in the sequence, which is ... The subtraction is because ... . Hence, for ; ... which, after simplifying,
gives the recurrence
(b) Find a recurrence relation and initial conditions for , the number of sequences of length of upper case letters that do not contain GOAL.