Find a recurrence relation for the number of quaternary (4base digits) sequences with no copy of $3000$ as a subsequence.
Workings:
First digit $0, 1, 2$ Proceed as normal:
$3a_{n-1}$
If first digit is $3$ next number can be can be $0, 1, 2$
$3a_{n-2}$
If 3, 0 then
$3a_{n-3}$
If 3, 0 , 0. There can't be another 0
$2a_{n-4}$
This gives:
$a_n = 3a_{n-1} + 3a_{n-2} + 3a_{n-3} + 2a_{n-4}$
I don't believe this is correct. Any help will be appreciated.
The set of quaternary sequences without the sub-sequence $3000$ can be parsed by following regular expression
$$\big(0^*(3|30|300)^*(1|2)\big)^*0^*(3|30|300)^*\tag{*1}$$
where $S^*$ stands for the Kleene star for the set of strings $S$. Based on this regular expression, we can read off the corresponding OGF (ordinary generating function). The rules one need to know are:
if $g_A(t)$, $g_B(t)$ are OGF for pattern $A$ and $B$, the OCF for
Following these rules,
$$\begin{array}{rcl} 0^* &\leadsto& 1 + t + t^2 + \ldots = \frac{1}{1-t}\\ (3|30|300) &\leadsto& t + t^2 + t^3 = \color{red}{\frac{t-t^4}{1-t}}\\ (3|30|300)^* &\leadsto& \frac{1}{1- \color{red}{\frac{t-t^4}{1-t}}} = \frac{1-t}{1-2t+t^4}\\ 0^*(3|30|300)^* &\leadsto& \left(\frac{1}{1-t}\right)\left(\frac{1-t}{1-2t+t^4}\right) = \color{green}{\frac{1}{1-2t+t^4}}\\ 0^*(3|30|300)^*(1|2) &\leadsto& \left(\color{green}{\frac{1}{1-2t+t^4}}\right) 2t = \color{blue}{\frac{2t}{1-2t+t^4}} \end{array}$$
Combine these, the OGF for $(*1)$ is given by
$$\text{OCF}_{3000}(t) = \sum_{n=0}^\infty a_n t^n = \left(\frac{1}{1 - \color{blue}{\frac{2t}{1-2t+t^4}}}\right)\left(\color{green}{\frac{1}{1-2t+t^4}}\right) = \frac{1}{1-4t+t^4}\tag{*2}$$
This implies the sequence $a_n$ satisfies a recurrence relation of the form: $$a_n = \begin{cases} 4a_{n-1} - a_{n-4}, &n > 0,\\ 1, & n = 0,\\ 0, & n < 0 \end{cases} $$ One can then use this to determine the values of $a_n$ recursively.
$$(a_0,a_1,\ldots) = (1,4,16,64,255,1016,4048,16128,64257,256012,1020000,\ldots)$$
Update
About the question whether there is a simpler argument that give us the same answer.
For this particular problem, the answer is yes but there is a catch!
Given any sequence, we will call it admissible if it is quaternary and didn't contain the sub-sequence $3000$. It is clear:
Given any admissible sequence of length $n$, if one remove the leading digit, we get an admissible sequence of length $n-1$.
Conversely, given any admissible sequence of length $n-1$, if we prepend it with a quaternary digit, we will get back an admissible sequence of length $n$ as long as the digit we add is not $3$ and the original sequence didn't begin with $000$.
Since the sub-sequence $000$ doesn't contain the digit $3$, prepend it or delete it from the "head" of a sequence won't change its status of admissibility. This means there is a $1$-$1$ correspondence between admissible sequence of length $n-1$ with prefix $000$ and admissible sequence of length $n-4$.
Combine these, one obtain the same recurrence relation as before
$$a_n = 4 a_{n-1} - a_{n-4},\quad\text{ for } n > 4\tag{*3}$$
What is the catch? The catch is in step $3$.
When we analysis problem like this, it is easy to forget the $1$-$1$ correspondence between the admissible sequence of length $n-1$ with a specific prefix of length $k$ and admissible sequence of length $n-1-k$ is not guaranteed.
If the prefix contains the leading digit, $(*3)$ can fail. For example, if we replace the excluded sub-sequence $3000$ by $3030$, the OCF is no longer that in $(*2)$. Instead, it becomes
$$\begin{align} \text{OCF}_{3030}(t) &= \frac{1+t^2}{1-4t+t^2-4t^3+t^4}\\ &= 1+4t+16t^2+64t^3+255t^4+1016t^5+4049t^6+16136t^7+\cdots \end{align}$$