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?
Consider a representation with even number of zeros at step $n-1$. At the next step $n$, you can construct $3$ even number of zeros by following it with $1,2,3$. Similarly if you have a representation with odd number of zeros, you have to follow it with $0$ to keep it still even $0$s.

So at $i$th step let $n_{odd,i}$ be the number of odds and $n_{even,i}$ be the number of even. We have that
\begin{equation}
n_{even,i+1}=3n_{even,i}+n_{odd,i},~n_{odd,i+1}=3n_{odd,i}+n_{even,i}
\end{equation}
These are your recurrence relations. The starting point is $n_{even,1}=3$, $n_{odd,1}=1$.

You can verify by induction that $n_{even,i}=2^{i-1}(1+2^i)$ is the general formula.
Its:

$3^n$ ...... no occurence of 0

$+3^{n-2}(\binom{n-1}1)$ ...... occurence of two consecutive 0's

$+3^{n-2}(\binom{n-1}2)$ ...... occurence of two separated 0's

$+3^{n-4}(\binom{n-3}1+\binom{n-3}2\binom{3}1+\binom{n-3}3\binom{3}2+\binom{n-3}4\binom33) $ ..... occurence of 4 gathered or separated 0's

$+...$

$+3^{n-2k}(\binom{n-2k+1}1+\binom{n-2k+1}2\binom{2k-1}1+\binom{n-2k+1}3\binom{2k-1}2+\binom{n-2k+1}4\binom{2k-1}3 ....) $

$+...+1$   where all sequence is filled by 0's



for n=1:20;
h=0;for k=n:-2:1
a=3^k;v=1;s=0;
while (v&lt;=n-k+1)&amp;(v&lt;=k)
s=s+nchoosek(n-k+1,v)*nchoosek(k-1,v-1);v=v+1;
end
h=a*s+h;
end
fprintf('%d ',h+mod(n+1,2));
end



Writing this piece of code through matlab gives following results:



  3 10 36 136 528 2080 8256 32896 131328 524800 2098176 8390656 33558528 134225920 536887296 


which matches OEIS A007582