Chapter 8.4, Problem 52E

A coding system encodes messages using strings of base 4 digits (that is, digits from the set {0,1,2,3}). A codeword is valid if and only if it contains an even number of 0s and an even number of 1s. Let a_nequal the number of valid codewords of length n. Furthermore, let b_n. c_n, and d_nequal the number of strings of base 4 digits of length n with an even number of 0s and an odd number of 1s, with an odd number of 0s and an even number of 1s, and with an odd number of 0s and an odd number of 1s, respectively.

a) Show that $d_n=4^n-a_n-b_n-c_n$ . Use this to show that $a_{n+1}=2a_n+b_n+c_n,b_{n+1}=b_n+c_n+4^n$, and $c_{n+1}=c_n-b_n+4^n$.

b) What area $a_1,b_1,c_1$ , and $d_{\text{1}}$ ?

c) Use parts (a) and (b) to find ${\text{a}}_{\text{3}},b_3,c_3$, and $d_3$.

d) Use the recurrence relations in part (a), together with the initial conditions in part (b), to set up three equations relating the generating functions A(x), B(x), and C(x) for the sequences $\left\{a_n\right\},\left\{b_n\right\}\text{,}$ ,and $\left\{C_n\right\}$, respectively.

e) Solve the system of equations from part (d) to get explicit formulae for A(x), 8(x), and C(x) and use these to get explicit formulae for ${\text{a}}_n,b_n,c_n$ , and $d_n$.