Find the Recurrence relation for $q_n$ given the following condition:

Question

Let $q_n$ denote the number of strings of length $n$ (formed from digits 0,1,2,3) which have even number of $2$'s. set up a recurrence relation for $q_n$.

Answer 1

Indeed it can be defined by two recurrence. Suppose $p_n$ is the number of strings which have odd 2's. Now we have: $$q_n = 3q_{n-1} + p_{n-1}$$ $$p_n = q_{n-1} + 3 p_{n-1}$$

Now we can unified them by matrix operation by $T_n = \begin{bmatrix}q_n \\ p_n \end{bmatrix}$:

$$T_n=\begin{bmatrix}3 & 0 \\ 0 & 1 \end{bmatrix}T_{n-1}+\begin{bmatrix}0 & 1 \\ 3 & 0 \end{bmatrix}T_{n-1}=\begin{bmatrix}3 & 1 \\ 3 & 1 \end{bmatrix}T_{n-1}.$$

Now we can say $T_n = \begin{bmatrix}q_n \\ p_n \end{bmatrix} = \begin{bmatrix}3 & 1 \\ 3 & 1 \end{bmatrix}^{n-1}T_1$. We can compute that $T_1 = \begin{bmatrix}3 \\ 1 \end{bmatrix}$, and $$T_n = \begin{bmatrix}3 & 1 \\ 3 & 1 \end{bmatrix}^{n-1}\begin{bmatrix}3 \\ 1 \end{bmatrix}$$