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?
 A: 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.
A: Here is a different approach: 
Let $0$ have weight $x$, and let $1$,$2$, $3$ have weight $1$ each. The weight of a word over $\{0,1,2,3\}$ is the product of the weights of its letters. The total weight of all one-letter words is then $x+1+1+1=3+x$, and the total weight of all $n$-letter words is $(3+x)^n$. It follows that the total weight of all $n$-letter words with an even number of ixes is given by
$$f_n(x):={1\over2}\bigl((3+x)^n+(3-x)^n\bigr)\ .$$
Putting $x=1$ here  gives each occurring letter  the weight $1$, hence counts all words with weight $1$. It follows that
$$T(n)=f_n(1)={1\over2}(4^n+2^n)\ .$$
A: 
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*}

A: 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<=n-k+1)&(v<=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
