Counting with Recurrence Relations

Question

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,... .

Answer 1

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}$