[Math] Recurrence relation for the number of strings of length $n$ in base $3$

Question

How can we find a recurrence relation for the number of strings of length $n$ in base $3$ such that the number of $1$'s and $2$'s are odd?

Answer 1

Let $a_n$ be the number of ternary strings of length $n$ having an odd number of $1$’s and an odd number of $2$’s. (Call such strings good strings.) Let $b_n$ be the number of ternary strings of length $n$ having an odd number of $1$’s and an even number of $2$’s, let $c_n$ be the number of ternary strings of length $n$ having an even number of $1$’s and an odd number of $2$’s, and let $d_n$ be the number of ternary strings of length $n$ having an even number of $1$’s and an even number of $2$’s.

Suppose that $\sigma$ is a good string of length $n\ge 2$, and $\tau$ is the substring consisting of the first $n-2$ digits of $\sigma$. If the last two digits of $\sigma$ are $00,11$, or $22$, then $\tau$ is counted in $a_{n-2}$. If the last two digits of $\sigma$ are $02$ or $20$, then $\tau$ is counted in $b_{n-2}$. Continuing this analysis leads to the conclusion that

$$\begin{align*} a_n&=3a_{n-2}+2b_{n-2}+2c_{n-2}+2d_{n-2}\\ &=a_{n-2}+2(a_{n-2}+b_{n-2}+c_{n-2}+d_{n-2})\;, \end{align*}$$

where the quantity in parentheses is easily evaluated explicitly to give the desired recurrence.