Combinatorial Recursion Define a recursion that gives the number of sequences that include the numbers $0,1,2,3$ with an even number of $1$'s and an even number of $0$'s. 
So far I got $$a(n) = 2a(n-1) + 2a(n-2)$$ which shows that a sequence of length $n$ is the sum of sequences of length $n-1$ times two (since each of length $n-1$ can have a $2$ or $3$ added to it) plus two times all sequences of length $n-2$ because you can add $00$ or $11$ to those (since you need an even number of each), but I have no idea how to permute the $0$s and $1$s in the sequence in different ways other than pairs of $00$ and $11$. 
 A: We interpret the question as asking how many words of length $n$ there are over the alphabet $\{0,1,2,3\}$ that have an even number of $0$'s and an even number of $1$'s. Call these good words. Note that there is a total of $4^n$ words of length $n$.
Let $a_n$ be the number of sequences of length $n$ that have an even number of $0$'s and an even number of $1$'s. We are only interested in $a_n$, but in this kind of problem it can be useful to introduce close relatives of what we are looking for. 
Let $b_n$ be the number of words of length $n$ such that the number of $0$'s is even, and the number of $1$'s is odd, or the other way around.
Finally, let $c_n$ be the number of words of length $n$ with an odd number of $0$'s and an odd number of $1$'s.
We have $a_{n+1}=2a_n+b_n$. For we can make a "good" word by adding $2$ or $3$ to a good word, or by adding a $0$ or a $1$, whichever is appropriate, to a word that has an even number of one of $0$ or $1$ and an odd number of another.
But $b_{n+1}=2a_n+2b_n+2c_n=2\cdot 4^n$. This is because there are several ways to make a word of length $n+1$ with the number of $0$'s and the number of $1$'s of different parity. We can add a $0$ or a $1$ to a good word of length $n$. Or we can add a $2$ or a $3$ to a word of type (b). Or we can add a $0$ or a $1$ to a word of type (c). 
It follows that
$$a_{n+1}=2a_n+2\cdot 4^{n-1}.$$
Remark: The above is a recursion that only involves the $a_i$. It can be somewhat nicer to give simultaneous recursions for the $a_i$, $b_i$, and $c_i$. 
Note that $c_{n+1}=b_n+2c_n$. If $V_i$ is the vector $(a_i,b_i,c_i)$, we can easily find a matrix $M$, with constant entries, such that $V_{n+1}=MV_n$. This is a useful general technique. We can then get valuable information by using tools from linear algebra. 
