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
= 4
n
−
an
−
bn
−
cn
. Use this to show that
an
+
1= 2an
+
bn
+
cn, bn
+
1=
bn
−
cn
+ 4
n
, and
cn
+
1=
cn
−
bn
+ 4
n
.
b) What are
a
1
, b
1
, c
1
,
and
d
1?
c) Use parts (a) and (b) to find
a
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 {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.