A coding system encodes messages using strings of base 4 digits (that is, digits from the set {0, 1, 2, 3}). A code word is valid if and only if it contains an even number of 0s and an even number of 1s. Let an equal the number of valid code words of length n. Furthermore, let bn, cn, and dn equal 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 dn = 4n − an− bn− cn. Use this to show that an+1= 2an + bn+ cn, bn+1= bn− cn+ 4n, and cn+1= cn− bn+ 4n.
b) What are a1, b1, c1, and d1?
c) Use parts (a) and (b) to find a3, b3, c3, and d3.
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 {an}, {bn}, and {cn}, respectively.
e) Solve the system of equations from part (d) to get explicit formulae for A(x), B(x), and C(x) and use these to get explicit formulae for an, bn, cn, and dn.