The letter A appears an even number of times. How many different sequences could Dr. Lizardo have written down? 
Dr. Lizardo writes down a sequence of $n$ letters, where each letter is A, B, or C, and the letter A appears an even number of times. How many different sequences could Dr. Lizardo have written down?


What I have tried so far
The last letter is predefined in terms of "A or not" based on the first $n-1$ letters. If there are an odd number of As so far, the last one has to be A, otherwise, B or C. Therefore, there are $3^{n-1}$ ways to write the first $n-1$ letters. However, the last letter can either have 1 choice or 2 choices.
I am thinking maybe we need to do $S_n = 3^{n-1} + S_{n-1}$. However, I need a closed form, not a recurrance. How can I do this?
Thank you!

Note: $S_n = 3^{n-1} + S_{n-1}$ seems to be working for the first few values of $n$ (I tested through $n=4$), so finding a closed form of that recurrance would work as well.

This is a bit more of a linear algebra proof which is probably not what you are seeking but I'd still like to share it anyways. Define two sequences $a_n$ being the number of length-$n$ sequences with even number of As and $b_n$ being the number of length-$n$ sequences with odd number of As. Clearly $a_0 = 1$ and $b_0 = 0$
Notice that the if you have an length-$(n-1)$ sequences with even number of As: there are two ways to add one character (either B or C) so that the new length-$n$ sequence has even As and there is one way to add one character (A) so that the new length-$n$ sequence has odd As.
Similarly if you have an length-$(n-1)$ sequences with odd number of As: there is one way to add one character (A) so that the new length-$n$ sequence has even As and there are two ways to add one character (B or C) so that the new length-$n$ sequence has odd As.
From here we can define a recurrence relation in terms of matrices
$$ \left( \begin{matrix} a_{n} \\ b_{n} \end{matrix} \right) =
\left( \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \right)
\left( \begin{matrix} a_{n-1} \\ b_{n-1} \end{matrix} \right) =
\left( \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \right)^n
\left( \begin{matrix} a_{0} \\ b_{0} \end{matrix} \right)$$
If we diagonalize this matrix we get
$$ \left( \begin{matrix} 2 & 1 \\ 1 & 2 \end{matrix} \right) =
\left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right)
\left( \begin{matrix} 1 & 0 \\ 0 & 3 \end{matrix} \right)
\frac{1}{2} \left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right)$$
$$ \left( \begin{matrix} a_{n} \\ b_{n} \end{matrix} \right) =
\left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right)
\left( \begin{matrix} 1 & 0 \\ 0 & 3^n \end{matrix} \right)
\frac{1}{2} \left( \begin{matrix} -1 & 1 \\ 1 & 1 \end{matrix} \right)
\left( \begin{matrix} 1 \\ 0 \end{matrix} \right) = 
\frac{1}{2} \left( \begin{matrix} 3^n+1 \\ 3^n-1 \end{matrix} \right)$$
thus $a_n = \frac{3^n+1}{2}$
