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

Question

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.

Answer 1

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}.$$

Answer 2

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}\;.$$