This is the first time working through a word problem with recurrence relations and I am looking to see if my workings are correct, or if there is another way to complete this problem
Find a recurrence relation for the number of $n$-letter sequences using the letters $A, B, C$ such that any $A$ not in the last position of the sequence is always followed by a $B$.
Say there are $a_n$ such sequences.
Case 1
(Starts with C): The remaining $n-1$ letters must follow the original rule, so $a_{n-1}$ ways.
Case 2
(Starts with B): The remaining $n-1$ letters must follow the original rule, so $a_{n-1}$ ways.
Case 3
(Starts with A): The second letter must be B, and the remaining $n-2$ letters must follow the original rule, so $a_{n-2}$ ways.
So $a_n = 2a_{n-1} + a_{n-2}$, with initial conditions $a_0 = 1$, $a_1 = 3$.
It looks good to me.
To answer OP's question in the comments: "could someone explain why $a_0=1,a_1=3$":
When $n=0$, there is one $0$-letter sequence, the empty sequence $( )$. So we have $a_0=1$.
When $n=1$, there are $3$ one-letter sequences that satisfy the criteria: $(A)$, $(B)$, and $(C)$, so we have $a_1=3$.
Two initial conditions, $n=1$ and $n=0$, are needed because our recurrence relation involves two previous terms. If we were to just use $n=0$ as an initial condition, $a_{n-2}$ would not always be well-defined (for example, if we wished to find $a_1$ by evaluating $a_1=2a_0+a_{-1}$).