Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with

Question

Find a system of recurrence relations foe computing the number of n-digit quaternary sequences with (a) An even number of 0s (b) An even total number of 0s and 1s (c) An even number of 0s and an even number of 1s

Answer 1

$(a)$ Let:

\begin{eqnarray*} a_n && \text{be the number of $n$-digit quaternary sequences with an even number of $0$s} \\ b_n && \text{be the number of $n$-digit quaternary sequences with an odd number of $0$s.}\end{eqnarray*}

By considering what the addition of one more digit will do to an $(n-1)$-digit sequence, we see that the relationships are:

\begin{eqnarray*} a_n &=& 3a_{n-1} + b_{n-1} \\ b_n &=& a_{n-1} + 3b_{n-1}. \end{eqnarray*}

The initial case:

\begin{eqnarray*} a_1 &=& 3 \\ b_1 &=& 1.\end{eqnarray*}

$(b)$ Similarly, let $a_n$ and $b_n$ denote the number of "even" and "odd" $n$-digit sequences, respectively.

By similar reasoning as in $(a)$, we see the relationships are:

\begin{eqnarray*} a_n &=& 2a_{n-1} + 2b_{n-1} \\ b_n &=& 2a_{n-1} + 2b_{n-1}. \end{eqnarray*}

The initial case has $a_1 = b_1 = 2$.

It's clear from this that $a_n=b_n$ for all $n$, so this pair of equations reduces to

\begin{eqnarray*} a_n &=& 4a_{n-1}. \end{eqnarray*}

$(c)$ Let:

\begin{eqnarray*} a_n && \text{be the number of "even-even" $n$-digit sequences} \\ b_n && \text{be the number of "even-odd" or "odd-even" $n$-digit sequences} \\ c_n && \text{be the number of "odd-odd" $n$-digit sequences.} \end{eqnarray*}

Again, by considering what the addition of one more digit will do to an $(n-1)$-digit sequence, we see that the relationships are:

\begin{eqnarray*} a_n &=& 2a_{n-1} + b_{n-1} \\ b_n &=& 2a_{n-1} + 2b_{n-1} + 2c_{n-1} \\ c_n &=& b_{n-1} + 2c_{n-1}. \\ \end{eqnarray*}

The initial case has $a_1 = 2,\; b_1 = 2,\; c_1 = 0$.