Let $a_n,b_n$ denote number of sequence with $n$ terms formed by $1,2,3,4$ that contain even,odd number of digit $1$ respectively We have $a_{n+1}=b_n+3a_n$ and $b_{n+1}=a_n+3b_{n}$ So $a_{n+2}-3a_{n+1}=a_n+3(a_{n+1}-3a_n)$, so $a_{n+2}=6a_{n+1}-8a_n$, then the rest is easy.

Mhm, this one took me a lot longer than #1-#3. We'll just do the problem for a general $n$. We claim the solution to be $\tbinom{2^n+1}{2}$. Let $a_n$ denote the number of possible sequences with $n$ terms. We'll induct. BASE CASE: Obviously for $n=1$ we have $a_1=3=\tbinom{2+1}{2}$. INDUCTION STEP: Assume $a_n = \tbinom{2^n+1}{2}$. We'll show $a_{n+1}=\tbinom{2^{n+1}+1}{2}$. Consider a sequence with $n+1$ terms \[ x_1,x_2,x_3,x_4,\dots,x_n,x_{n+1} \]There are $a_n$ possibilities such that there is an even number of $1$'s among the numbers $x_1,x_2,\dots,x_n$. Then, there are $3$ possibilities to choose $x_{n+1}$ to preserve that parity. Evidently, there are $4^n-a_n$ possibilities such that there is an odd number of $1$'s among the numbers $x_1,x_2,\dots,x_n$. Then we'll choose $x_{n+1}=1$. Thus \[ a_{n+1}=3a_n+ \left(4^n-a_n \right) = 2a_n+4^n. \]Now, it is easy to finish the induction. Observe \[ a_{n+1}=2 \cdot \binom{2^n+1}{2}+4^n = \left(2^n+1 \right) \cdot 2^n + 4^n = 2^{2n+1}+2^n = \binom{2^{n+1}+1}{2}. \]That finishes the induction step which which we are done. So our answer is $a_{2016}=\tbinom{2^{2016}+1}{2}$.