Denote by $a_n$ the number of sequences of length $n$ consisting of letters from the set $\{A,B,C\}$ such that no two letters $A$ are consecutive.
Find integers $p$ and $q$ such that for all $n\ge1$ the following equality holds:
$$a_{n+2}=pa_{n+1}+qa_n$$
I found that $p=q=2$ by finding $a_1, a_2, a_3$ and guessing.
I want to know how to find what $p$ and $q$ are using math, instead of guessing what they are because I have trouble with thinking through these types of problems.
What I originally thought was if we have $a_2$, and the second letter is $A$, to find $a_3$ we have two options for the third letter, $B$ or $C$, if the second letter of $a_2$ is not $A$ then we have three options for what the third letter can be in $a_3$, so I understand how $a_{n+2}$ is related to $a_{n+1}$ but I do not know how $a_{n+2}$ is related to $a_n$?
Hint: any string fulfilling the given constraints can only be something of the form $B*$, $C*$, $AB*$ or $AC*$ (with $*$ being a valid string with the proper length), hence $a_{n}=2a_{n-1}+2a_{n-2}$ for any $n\geq 3$.