The letter A appears an even number of times. How many different sequences could Dr. Lizardo have written down?
Setting $S_0 = 1$ (the empty sequence definitely has an even number of 'A's) and then defining $S_n = 3^{n-1} + S_{n-1}$ for $n \geq 1$ gives $$S_n = S_0 + \sum_{k=0}^{n=1}3^k = 1 + \frac{1-3^n}{1-3} = \frac{3^n+1}{2}$$
where we have used the formula for the finite geometric series $$\sum_{k=0}^{n-1}ar^k = \frac{a(1-r^n)}{1-r}$$
Another way to see this is to use generating functions: $$P(x,y,z) = (x+y+z)^n = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n}} S(i,j,k)x^iy^jz^k$$ is the generating function for the number of sequences $S(i,j,k)$ with $i$ 'A's, $j$ 'B's, and $k$ 'C's. We want to find $$\sum_{\substack{i,j,k \geq 0 \\ i+j+k=n \\ 2|i}} S(i,j,k)$$
To impose the assumption that $i$ is even, we take the even part with respect to $x$: $$\frac{P(x,y,z) + P(-x,y,z)}{2} = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n \\ 2|i}} S(i,j,k)x^iy^jz^k$$
and then we just evaluate at $x=y=z=1$: $$\frac{(1+1+1)^n + (-1+1+1)^n}{2} = \sum_{\substack{i,j,k \geq 0 \\ i+j+k=n \\ 2|i}} S(i,j,k)$$
which we note simplifies once again to $\frac{3^n+1}{2}$
Good analysis, but a closed form requires that you get down in the mud.
Note : possible exception is if someone can provide a more elegant computation than my kludgy approach.
Let $c = \lfloor \frac{n}{2}\rfloor.$
That is $c$ is the largest integer such that $2c \leq n$.
Then, you want
$$\sum_{k=0}^c f(k)$$,
where $f(k)$ is the exact # of ways of having $2k$ A's in the sequence.
There are $\binom{n}{2k}$ ways of distributing the $2k$ A's.
There are $2^{(n-2k)}$ ways of choosing B or C for the $(n - 2k)$ other slots.
Therefore,
$$f(k) = \binom{n}{2k} \times 2^{(n-2k)}.$$
It is unclear to me whether the summation can be expressed in a simpler fashion.
Consider two cases.
Case 1. The sequence is all C's. There is just one such sequence, and it has an even number of A's, namely zero.
Case 2. The sequence is not all C's. There are $3^n-1$ such sequences, and exactly half of them, or $\frac{3^n-1}2$, have an even number of A's. To see this, look at the leftmost letter in the sequence that's not a C; toggling it between A and B, we see that there's a one-to-one correspondence between sequences with an even and an odd number of A's.
Combining the results from Case 1 and Case 2, we get a grand total of $$1+\frac{3^n-1}2=\frac{3^n+1}2.$$
More generally, over an alphabet of $k$ letters, the number of sequences of length $n$ in which a certain letter appears an even number of times is $$(k-2)^n+\frac{k^n-(k-2)^n}2=\frac{k^n+(k-2)^n}2;$$ see my answer to this question.