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}.$$
Best Answer
Hint: One approach is to define four functions. Let $OE(n)$ be the number of words of length $n$ which have an odd number of $1$'s and an even number of $2$'s and three similar ones. Write the recurrence relations between these four. They stay closely balanced, so they are all just about $\frac {3^n}4$ in each one. Maybe you can find a proof of the small correction (note that this is not an integer, which the final result must be)
Added: you are right that $EO(n)=OE(n)$ by symmetry. That is a good thing to think about, as it gets you down to three functions. You need to write a recurrence for each function separately. A word where both are odd can come from a word where both are odd by adding a 3, from EO by adding a 1, or from OE by adding a 2. So $OO(n)=EO(n-1)+OE(n-1)+OO(n-1)$ Your starting condition is $EE(0)=1, \text{others}(0)=0$ because the empty word is even in both. I made a spreadsheet to calculate the first dozen values or so. You can then see a pattern in the corrections, which you can prove from the recurrences. Your final answer is then $EO(n)$