recurrence relation homework question

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.

Answer 1

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.

Answer 2

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)$.