How to form a recurrence for a $n$-digit sequence using digits $0,1,2,3$ so that we have even no of $0$'s? If we assume $T(n)$ to be the function representing the case where we have even number of $0$'s then $T(1)=3$ precisely strings $1, 2$ and $3$.
$T(2)= 10$ ($00,11,22,33,12,21,13,31,23,32$). Likewise I got $T(3)=36$ and $T(4)=124$. 
Now how to proceed from here?


Here   is a variation of the  theme based upon regular expressions. We can describe all  valid   strings  as
  \begin{align*}
(0(1+2+3)^*0+1+2+3)^*
\end{align*}

Comment:


*

*Valid strings consist  of   zero   or more occurrences of $1$ or $2$ or $3$    or  

*when  we start with a $0$ it has to be followed by another $0$  possibly with zero    or  more occurrences of $1,2$ or $3$ in between.
This was the  hard part, namely finding an appropriate regular  expression. Everything what  follows is a  matter of  technique.
Using the notation from P. Flajolet's and R. Sedgewicks Analytic Combinatorics with the sequence $SEQ(x)$ defined as
\begin{align*}
  SEQ(x)=1+x+x^2+\cdots=\frac{1}{1-x}
  \end{align*}

we can translate  the regular expression   into  the  generating function
\begin{align*}
  SEQ&(xSEQ(3x)x+3x)\\
&=\frac{1}{1-\left(\frac{x^2}{1-3x}+3x\right)}\\
  &=\frac{1-3x}{1-6x+8x^2}\\
  &=1+3x+10x^2+36x^3+136x^4+\cdots
  \end{align*}

We use the  coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain the  wanted sequence numbers $T(n)$ by partial fraction decomposition  of  the generating series
  \begin{align*}
T(n)&=[x^n]\frac{1-3x}{1-6x+8x^2}\\
&=[x^n]\left(\frac{1}{2(1-4x)}+\frac{1}{2(1-2x)}\right)\\
&=[x^n]\frac{1}{2}\sum_{k\geq 0}4^kx^k+[x^n]\frac{1}{2}\sum_{k\geq 0}2^kx^k\\
&=\frac{1}{2}\left(4^n+2^n\right)
\end{align*}

