Counting with Recurrence Relations Find the recurrence relation for a(n) - number of ternary strings of length n, containing the number 2 odd times.
Some of these: 012,112,12,02,... .
 A: We divide all that sequences into $4$ non-intersecting subclasses:
a) Odd count of $2$s, ends with $1$ or $0$,
b) Even count of $2$s, ends with $1$ or $0$,
c) Odd count of $2$s, ends with $2$,
d) Even count of $2$s, ends with $2$,
Let $a_n,\,b_n,\,c_n,\,d_n$ be the cardinality of a corresponding class of sequences of length $n$. For $n=1$ we have
$$a_1=0,\,b_1=2,\,c_1=1,\,d_1=0$$
Let $n>1$. We consider the last digit and the rest part of length $n-1$.
If a sequence is of classes a or b, then the rest part will have the same amount of $2$s, therefore
$$a_n=2(a_{n-1}+c_{n-1})\\b_n=2(b_{n-1}+d_{n-1})$$
Otherwise the rest part will have one less $2$, thus
$$c_n=b_{n-1}+d_{n-1}\\d_n=a_{n-1}+c_{n-1}$$
Let $\mathbf{x}_n=(a_n,b_n,c_n,d_n)^T$, we have $\mathbf{x}_n=A\mathbf{x}_{n-1}$ where
$$A=\begin{pmatrix}
2&0&2&0\\
0&2&0&2\\
0&1&0&1\\
1&0&1&0
\end{pmatrix}$$
Performing diagonalization of $A$ we have $A=SDS^{-1}$ where
$$S=\begin{pmatrix}
0 & -1 & 2 & 2\\
-1 & 0 & -2 & 2\\
0 & 1 & -1 & 1\\
1 & 0 & 1 & 1
\end{pmatrix}\\
D=\operatorname{diag}(0,0,1,3)$$
As $\mathbf{x}_n$ $=A^{n-1}\mathbf{x}_1$ $=SD^{n-1}S^{-1}\mathbf{x}_1$ the desired value will be $(1,0,1,0)\cdot \mathbf{x}_n$ $=
(1,0,1,0)\cdot SD^{n-1}S^{-1}\mathbf{x}_1$ $=\frac{3^n-1}{2}$
