Sequences of $n$ letters where each letter is $A$, $B$, or $C$ and the letter $A$ appears an even number of times.

Question

I found the recursive form which is $S_1=2, 3\cdot S_{n-1}-1=S_n$ but I'm not sure how to continue.

Answer 1

bof’s comment leads to a very elegant solution, but you can also simply solve the recurrence to get a closed form for $S_n$. There are many ways to do so, but one very simple technique seems especially natural here.

Notice that your sequence is almost geometric. There’s a trick that you can use with simple recurrences like this to turn the recurrence into one that really is geometric (or if you prefer, exponential). Let $x_n=S_n-d$ for some constant $d$ as yet to be determined. Then $S_n=x_n+d$, and you can rewrite your recurrence as

$$x_n+d=3(x_{n-1}+d)-1=3x_{n-1}+3d-1\,,$$

or

$$x_n=3x_{n-1}+2d-1\,,$$

Now let $d=\frac12$, so that $2d-1=0$, and you have the very simple recurrence $$x_n=3x_{n-1}\,,\tag{1}$$

whose solution is clearly $x_n=3^nx_0$.

$S_0=1$, since the empty sequence meets the requirements, so $x_0=1-\frac12=\frac12$, and the general solution to $(1)$ is $x_n=\frac12\cdot3^n$. Now recall that $x_n=S_n-\frac12$, so that

$$S_n=\frac12\cdot3^n+\frac12=\frac{3^n+1}2\,.$$