Let $w(n)$ denote the number of words of length $n$ over the alphabet $\{1,2,3\}$ with the restrictions that in a word the parity of $1$s be even and the parity of $2$s odd.
I have written out the possible words for some small values of $n$, hoping to see a relationship which would lead to a recurrence relation, but so far this has not helped. Trying to count the $w(n)$ by considering a general word $a_1a_2...a_n$ and counting possibilites for $a_i$ also doesn't seem to be a tractable solutions because of the dependency between the $a_i$. Any suggestions?
I am not looking for an answer to this problem, only for suggestions as to how one approaches a problem of this kind or for hints.
Following Ross Millikan's suggestion:
Define the functions $OO(n),OE(n),EO(n),EE(n)$, where the first digit represents the parity of $1$ and the second the parity of $2$. Then clearly
$w(n)=OO(n)+OE(n)+EO(n)+EE(n).$
Furthermore, $w(n)=3^n$ since each of the $n$ letters has three possible values. Now, one can define the function $s:OE(n)\rightarrow EO(n)$ by having it switch $1$ with $2$ and $2$ with $1$. Since this map is bijective, we have $OE(n)=EO(n)$. We can now derive a recurrence for $EO(n)$. An element of $EO(n)$ can be constructed from an element of $OO(n-1)$ by adjoining a $1$, from an element of $EE(n-1)$ by adjoining a $2$ and from $EO(n-1)$ by adjoining a $3$, which gives the recurrence
$EO(n)=OO(n-1)+EO(n-1)+EE(n-1).$
Using the relationship between our four functions and the symmetry between $EO(n)$ and $OE(n)$ we see that \begin{align*} EO(n)&=w(n-1)-OE(n-1)\\ &=3^{n-1}-EO(n-1). \end{align*} A closed form for this recurrence can be obtain by using the formula from this question by setting $b=-1,c=1$ and $d=3$, which gives
$EO(n)=\frac{3^n-(-1)^n}{4}.$