Can anyone help me finding recurrence relation in combinatoric? Guys, I am having trouble finding recurrent relation.
A codeword is made up of the digits $0,1,2,3$ (order is important!). A codeword is deﬁned as legitimate if and only if it has an even number of $0$’s. Let $a_n$ be the number of legitimate codewords of lenth $n$. Write a recurrence for $a_n$. 
The answer is $a_n = 3a_{n-1} + 4^{n-1} - a_{n-1}$
I know where $a_n=3a_{n-1}$ came from, but the problem is, I can't figure out where the 
rests ($4^{n-1} - a_{n-1}$) came from!
Please can anyone tell me how to approach the question?
Thank you!
 A: So lets look at a word $w = w_1 \ldots w_n$ of length $n$ with $w_i \in \{0,1,2,3\}$ and denote by $w' = w_2 \ldots w_n$ the word consisting of all but the first letter. $w$ is legimate in the following cases: 


*

*$w_1 \ne 0$ and $w'$ is legitimate (as then the number of $0$s in $w$ equals that in $w'$. There are 3 possiblities for $w_1$ and $a_{n-1}$ for $w'$, hence $3a_{n-1}$ for $w$ in this form.

*$w_1 = 0$, and $w'$ is illegitimate (as then the number of $0$s in $w'$ has to be odd) there are $4^{n-1}$ wors of 4 letters with length $n-1$, of which $a_{n-1}$ are legitimate, hence $4^{n-1}-a_{n-1}$ illegitimate. So $4^{n-1}-a_{n-1}$ possibilities for $w$ in this case.
A: Can use exponential generating functions (order is important, digits are labelled). For the digits 1, 2, 3 there are no restrictions:
$$
1 + \frac{z}{1!} + \frac{z^2}{2!} + \ldots + \frac{z^n}{n!} + \ldots
  = e^z
$$
For the digit 0 (only even number allowed):
$$
1 + \frac{z^2}{2!} + \frac{z^4}{4!} + \ldots + \frac{z^{2 n}}{(2 n)!} + \ldots
  = \frac{e^z + e^{-z}}{2}
$$
For the full codewords:
$$
(e^z)^3 \cdot \frac{e^z + e^{-z}}{2}
  = \frac{e^{4 z} + e^{2 z}}{2}
$$
The coefficient of $\frac{z^n}{n!}$ in this is seen to be:
$$
\frac{4^n + 2^n}{2}
$$
A: You can start defining $a_n$ as the number of legitimate words of length $n$, and $b_n$ the illegitimate of length $n$. Clearly $a_n + b_n = 4^n$. Also $a_0 = 1$, $b_0 = 0$.
To get a legitimate word of length $n + 1$, you can start with a legitimate one of length $n$ and add one of 3 digits, or start with an illegitimate one and add a zero (one option):
$$
a_{n + 1} = 3 a_n + b_n
$$
To get an illegitimate, from a legitimate add a zero (one way) or an illegitimate add one of 3 digits:
$$
b_{n + 1} = a_n + 3 b_n
$$
But we are done, we had $b_n = 4^n - a_n$ above, substituting this into the recurrence for $a_n$:
$$
a_{n + 1} = 3 a_n + 4^n - a_n
          = 2 a_n + 4^n
 \qquad a_0 = 1
$$
You could also say:
\begin{align}
a_{n + 2}
  &= 3 a_{n + 1} + b_{n + 1} \\
  &= 3 a_{n + 1} + (a_n + 3 b_n) \\
  &= 3 a_{n + 1} + a_n + 3 (a_{n + 1} - 3 a_n) \\
  &= 6 a_{n + 1} - 8 a_n
\end{align}
For initial conditions, $a_0 = 1$ and $a_1 = 3 a_0 + b_0 = 3$
