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.

Here we show the equality of two already given answers. The number $S_n$ is given by

\begin{align*}
\color{blue}{S_n=\frac{1}{2}\left(3^n+1\right)=\sum_{k=0}^n\binom{n}{2k}2^{n-2k}\qquad\qquad  n\geq 0}\tag{1}
\end{align*}

The following is valid
\begin{align*}
\sum_{k=0}^{n}\binom{n}{2k}x^{2k}+\sum_{k=0}^n\binom{n}{2k+1}x^{2k+1}&=(1+x)^n\\
\sum_{k=0}^{n}\binom{n}{2k}x^{2k}-\sum_{k=0}^n\binom{n}{2k+1}x^{2k+1}&=(1-x)^n\\
\sum_{k=0}^n\binom{n}{2k}x^{2k}&=\frac{1}{2}\left((1+x)^n+(1-x)^n\right)\tag{2}
\end{align*}

We obtain from (2)
\begin{align*}
\color{blue}{\sum_{k=0}^n\binom{n}{2k}2^{n-2k}}
&=2^n\sum_{k=0}^n\binom{n}{2k}\left(\frac{1}{2}\right)^{2k}\\
&=2^n\,\frac{1}{2}\left(\left(1+\frac{1}{2}\right)^n+\left(1-\frac{1}{2}\right)^n\right)\\
&=2^n\,\frac{1}{2}\left(\left(\frac{3}{2}\right)^n+\left(\frac{1}{2}\right)^n\right)\\
&\,\,\color{blue}{=\frac{1}{2}\left(3^n+1\right)}
\end{align*}
and the claim (1) follows.

