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}.$$ 
A: Generating functions are an unnecessary complication here.
Let $A_n$ be the set of $n$-digit ternary sequences whose sums are divisible by $3$, $B_n$ the set of $n$-digit ternary sequences whose sums leave a remainder of $1$ when divided by $3$, and $C_n$ the number of $n$-digit ternary sequences whose sums leave a remainder of $2$ when divided by $3$. Let $a_n=|A_n|,b_n=|B_n|$, and $c_n=|C_n|$.
Suppose that $\sigma\in A_n$, and let $\tau$ be the $(n-1)$-digit subsequence that remains when the last digit of $\sigma$ is removed. Exactly one of the following must be true:


*

*$\sigma$ ends in $0$, and $\tau\in A_{n-1}$;  

*$\sigma$ ends in $1$, and $\tau\in C_{n-1}$; or  

*$\sigma$ ends in $2$, and $\tau\in B_{n-1}$.


Moreover, each $\tau\in A_{n-1}$ yields a $\sigma\in A_n$ when a $0$ is appended to it, each $\tau\in C_{n-1}$ yields a $\sigma\in A_n$ when a $1$ is appended to it, and each $\tau\in B_{n-1}$ yields a $\sigma\in A_n$ when a $2$ is appended to it. That is, the number of sequences in $A_n$ that end in $0$ is $|A_{n-1}|=a_{n-1}$, the that end in $1$ is $|C_{n-1}|=c_{n-1}$, and the number that end in $2$ is $|B_{n-1}|=b_{n-1}$, so we have the recurrence
$$a_n=a_{n-1}+b_{n-1}+c_{n-1}\;.$$
You can use similar reasoning to derive recurrences
$$b_n=a_{n-1}+b_{n-1}+c_{n-1}$$
and
$$c_n=a_{n-1}+b_{n-1}+c_{n-1}\;.$$
Usually it takes a bit of work to solve systems of recurrences, but in this case it’s extremely easy: clearly $a_k+b_k+c_k=3^k$ for each $k\ge 0$, since each $k$-digit ternary sequence belongs to exactly one of the sets $A_k,B_k$ and $C_k$, and there are $3^k$ such sequences. Thus, the recurrences collapse to the closed form solution
$$a_n=b_n=c_n=3^{n-1}\;.$$
