Let $x_n$ be the number of words length n where the alphabet is made up of 1, 2, 3, 4 and there are always an odd number of 2's(for example, $x_1$ = 1 because there is only one word of length 1 with an odd number of 2's). Find a recurrence relation for $x_n$ = something.
How would I get it to be something like $x_n = x_{n-1} + x_{n-2}$. I solved for the first 3: $x_0 = 0$, $x_1 = 1$, and $x_2 = 6$, but I have no idea where to go from here.
Let $x_n$ be as you defined it and $y_n$ be the number of words with an even number of $2$'s. Then, $x_n = y_{n-1}+3x_{n-1}$ since we either start with a $2$ or not. And similarly, $y_n = x_{n-1}+3y_{n-1}$.
You can use these to get a recurrence relation for $x_n$.