# Recurrence relation for quaternary strings length n sum divisible by 3

#### sunrae

##### New member
Recurrence relation for The number of quaternary strings of length n for which the sum of all the entries is divisible by 3
I am not sure how to get the recurrence relation but I this is how I started.
All mod 3 Sum of entries is 0: a_n= 2a_{n-1}+c_{n-1}+b_{n-1}
Sum of entries is 1: b_n= 2B_{n-1}+c_{n-1}+a_{n-1}
Sum of entries is 2: c_n= 2c_{n-1}+a_{n-1}+b_{n-1}
Also know that 4^n = a_n + b_n + c_n
I believe the initial conditions are: a_0 = 1 and a_1 = 2

#### barrick

##### New member
Recurrence relation for The number of quaternary strings of length n for which the sum of all the entries is divisible by 3
I am not sure how to get the recurrence relation but I this is how I started.
All mod 3 Sum of entries is 0: a_n= 2a_{n-1}+c_{n-1}+b_{n-1}
Sum of entries is 1: b_n= 2B_{n-1}+c_{n-1}+a_{n-1}
Sum of entries is 2: c_n= 2c_{n-1}+a_{n-1}+b_{n-1}
Also know that 4^n = a_n + b_n + c_n
I believe the initial conditions are: a_0 = 1 and a_1 = 2
Hi sunrae,

You are almost there !

You have (correctly) written:
$$\displaystyle \displaystyle a_n = 2a_{n-1} + b_{n-1} + c_{n-1}$$

You also know that:
$$\displaystyle \displaystyle b_{n-1} + c_{n-1} = 4^{n-1} - a_{n-1}$$

You can now extract $$\displaystyle \textstyle b_{n-1} + c_{n-1}$$ from the second equation and substitute into the first.

There is also another technique, that looks more complicated. However, it is worth knowing it, for the following reasons:
• It can be used in similar problems, when the trick we used is not available.
• It gives you a recurrence with constant coefficients, and there is a lot of theory about these equations.
\displaystyle \displaystyle\begin{align} a_n &= 2a_{n-1} + b_{n-1} + c_{n-1}\\ b_n &= 2b_{n-1} + a_{n-1} + c_{n-1}\\ c_n &= 2c_{n-1} + a_{n-1} + b_{n-1} \end{align}

If you add the last two equations and write $$\displaystyle d_n = b_n + c_n$$ (because of the symmetry), you get:
\displaystyle \displaystyle\begin{align} a_n &= 2a_{n-1} + d_{n-1}\\ d_n &= 2a_{n-1} + 3d_{n-1} \end{align}

Now, write the equations, replacing $$\displaystyle n$$ with $$\displaystyle (n-1)$$:
\displaystyle \displaystyle \begin{align} a_{n-1} &= 2a_{n-2} + d_{n-2}\\ d_{n-1} &= 2a_{n-2} + 3d_{n-2} \end{align}

The idea is to eliminate $$\displaystyle d_{n-1}$$ and $$\displaystyle d_{n-2}$$ from these four equations.
The last two equations give you $$\displaystyle d_{n-1}= 3a_{n-1} -4a_{n-2}$$; substituting into the first, you get:
$$\displaystyle \displaystyle a_n = 5a_{n-1} - 4a_{n-2}$$

which is another recurrence relation.

Last edited: