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.


1 Answer 1


If $4^n = a_n + b_n + c_n$, then

$a_n = 2a_{n-1} + c_{n-1} + b_{n-1}$
becomes $a_n = 2a_{n-1} + (4^{n-1} - a_{n-1}) = 4^{n-1} +a_{n-1}$

which is indeed the recurrence you're looking for.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .