Explicit formula for number of n-digit ternary sequences with no consecutive 2's

Question

I'm looking for an explicit formula for $a_n$ which denotes the number of ternary sequences with no consecutive 2's. I've managed to find the recursive formula $$a_n = 2a_{n-1} + 2a_{n-2}$$ I've solved the characteristic equation and found the explicit formula $$a_n = A * (1+\sqrt{3})^n + B * (1-\sqrt{3})^n$$ And the basic conditions being $a_1 = 3$ and $a_2 = 8$. However, I cannot solve the system of equations to find the coefficients. I'd appreciate any help.

Answer 1

From the recursion: $a_2 = 2\cdot a_1 + 2\cdot a_0$, so $8 = 2\cdot 3 + 2a_0$, which gives $a_0 = 1$. Therefore we can write

$$a_1 = A\cdot(1+\sqrt{3}) + B\cdot(1-\sqrt{3}) = 3$$ $$a_0 = A\cdot(1+\sqrt{3})^0 + B\cdot(1-\sqrt{3})^0 = A + B = 1$$

We have a 2x2 linear system over $A,B$ with non null determinant (you can check), so it has a unique solution: $A=1/2 + \sqrt{3}/3, B = 1/2 -\sqrt{3}/3$