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
Please help! I also tried solving a system of equations but was unsuccessful.
Hi sunrae,
You are almost there !
You have (correctly) written:
an=2an−1+bn−1+cn−1
You also know that:
bn−1+cn−1=4n−1−an−1
You can now extract
bn−1+cn−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.
We start with the equations you wrote:
\(\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
dn=bn+cn (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
n with
(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
dn−1 and
dn−2 from these four equations.
The last two equations give you
dn−1=3an−1−4an−2; substituting into the first, you get:
an=5an−1−4an−2
which is another recurrence relation.