recurrence relation homework question This is a homework question
let $a_n$ number of n digit quaternary $(0,1,2,3)$ sequences in which there is never a$ 0 $anywhere to the right of a $3$. Solve for $a_n$
bot sure how to go about this. Could use help.
 A: Consider the first digit of an $n$-digit sequence. There are $2$ exhaustive and mutually exclusive cases to consider.
Case 1: Suppose the first digit is a $3$. Then the remaining $n-1$ digits must either be a $1$, $2$, or $3$ (none of them are allowed to be a $0$, since that $0$ would then be to the right of a $3$). Thus, there are $3^{n-1}$ possible sequences of this type.
Case 2: Suppose the first digit is a $0,1,$ or $2$. Then the subsequence of length $n-1$ to the right of the first digit must be a quaternary $(0,1,2,3)$ sequence in which there is never a $0$ anywhere to the right of a $3$ (there are no additional restrictions). Hence, there are $3a_{n-1}$ possible sequences of this type.
This yields the recurrence relation:
$$
a_n=3a_{n-1}+3^{n-1}
$$
You should be able to figure out the initial conditions and proceed from here.
A: Let $a_{n}(d)$ means the number of $n$ digit sequences, where $d$ parameter means if you can place a $0$ or not. We say if $d=0$ you can not place $0$, and $d=1$ otherwise. Then
If $n>0$
$$a_{n}(1)=3a_{n-1}(1)+a_{n-1}(0)$$
$$a_{n}(0)=3a_{n-1}(0)$$
with base case
$$a_{0}(1)=a_{0}(0)=1.$$
In $a_{n}(1)$ you can place any digit, but if you place $3$ digit, then you can not place $0$ digit anymore. In $a_{n}(0)$ you only can place $1,2,3$ digits.
Therefore your answer will be $a_{n}(1)$.
