Q:

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem:
Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple of 3.
I wish I could say that I have a general idea as far as how to solve this, but I don't. I've never dealt with simultaneous recurrence relations. It's in the section of the book that covers using generating functions, so I'm assuming I will need to be using one of those.   Any help would be appreciated.

A:

Here is a  different method that can help you  verify your answer once
you have found it. The generating function of these sequences is
$$f(z) = (1+z+z^2)^n.$$
With $\rho  = \exp(2\pi i/3)$ we can  extract the multiples  of three
using
$$\left.\frac{1}{3}(f(z)+f(\rho z)+f(\rho^2 z))\right|_{z=1}.$$
We get
$$\frac{1}{3} (3^n + (1+\rho+\rho^2)^n + (1+\rho^2+\rho)^n)
= 3^{n-1}.$$
Adddendum.  As  pointed  out  by @Brian.  M.  Scott  generating
functions are not the best approach here. If you insist it can be done
as follows.
Let  $a_n$  be  the  number  of ternary  sequence  with  digit  sum
congruent  to zero  modulo three,  $b_n$  congruent to  one and  $c_n$
congruent to two. We thus have  as our initial condition $a_0 = 1$ and
$b_0 = c_0 = 0.$ Introduce
$$A(z) = \sum_{n\ge 0} a_n z^n, \quad
B(z) = \sum_{n\ge 0} b_n z^n, \quad
\text{and}\quad
C(z) = \sum_{n\ge 0} c_n z^n.$$
Now we have the recurrences
$$a_n = a_{n-1} + b_{n-1} + c_{n-1}
\\ b_n = a_{n-1} + b_{n-1} + c_{n-1}
\\ c_n = a_{n-1} + b_{n-1} + c_{n-1}.$$
E.g.  we obtain  a  ternary sequence  on  $n$ symbols  with digit  sum
congruent to  one modulo three by  appending a one to  a sequence with
digit sum congruent to zero, a zero  to one congruent to one and a two
to one congruent to two.
Next  multiply these  recurrences  by $z^{n-1}$  and  sum over  $n$
ranging from one to infinity to get
$$\sum_{n\ge 1} z^{n-1} a_n
= \sum_{n\ge 1} z^{n-1} a_{n-1}
+ \sum_{n\ge 1} z^{n-1} b_{n-1}
+ \sum_{n\ge 1} z^{n-1} c_{n-1}$$
which is
$$\frac{1}{z} \sum_{n\ge 1} z^{n} a_n
= A(z) + B(z) + C(z)$$
or $$\frac{1}{z} (A(z) - 1) = A(z) + B(z) + C(z).$$
Similarly we get
$$\frac{1}{z} B(z) = A(z) + B(z) + C(z)$$
and
$$\frac{1}{z} C(z) = A(z) + B(z) + C(z)$$
These three equations may be re-written as
$$-1/z = A(z) (1-1/z) + B(z) + C(z)
\\ 0 = A(z) + B(z) (1-1/z) + C(z)
\\ 0 = A(z) + B(z) + C(z) (1-1/z).$$
This yields
$$-1/z = A(z)(-1/z) + B(z) 1/z
\\ 0 = A(z)(-1/z) + B(z)((1-1/z)^2 - 1).$$
We have $$-1/z = B(z) (1/z+2/z-1/z^2)$$
or $$B(z) = \frac{-1/z}{3/z-1/z^2}
= \frac{-z}{3z-1} = \frac{z}{1-3z}.$$
We also have $-1 = -A(z) + B(z)$ so
$$A(z) = 1 + B(z) = \frac{1-2z}{1-3z}$$
and finally $0 = \frac{1-z}{1-3z}  + C(z) (z-1)/z$
so that $$C(z) = \frac{z}{1-3z}.$$
Therefore the answer is
$$A(z) = \frac{1-2z}{1-3z},\quad
B(z) = \frac{z}{1-3z},\quad\text{and}\quad
C(z) = \frac{z}{1-3z}.$$
Extracting coefficients we get
$$[z^n] A(z) = 3^n  - 2\times 3^{n-1} = 3^{n-1},\quad
[z^n] B(z) = 3^{n-1},\quad\text{and}\quad
[z^n] C(z) = 3^{n-1}.$$ 

