In how many sequences on [0...4] the number of 0 is even? How do we solve this combinatorial question using recurrence?

In how many sequences consisting of $[0...4]$ of size $n$ the number of $0's$ is even?

 A: Call  sequences with an even number of $0$'s good, and the rest bad: a simplistic view of the world.
Let $a_n$ be the number of good sequences of length $n$, and let $b_n$ be the number of bad sequences of length $n$.
There is a simple relationship between $a_n$ and $b_n$. We will ignore it for now. One can get an alternate solution by not ignoring it.
Note that $a_{n+1}=4a_n +b_n$. For we can get a good sequence of length $n+1$ by appending any of $1$ to $4$ to a good sequence of length $n$, or by appending $0$ to a bad sequence.
Similarly, $b_{n+1}=a_n +4b_n$.
Use the above equations to eliminate $b_n$. We get
$$4a{n+1}-b_{n+1}=16a_n-a_n=15a_n.\tag{$1$}$$
In the equation $a_{n+1}=4a_n+b_n$, bump indices up by $1$. We get
$$a_{n+2}=4a_{n+1}+b_{n+1}.$$
Substituting the value of $b_{n+1}$ from $(1)$, we obtain
$$a_{n+2}=8a_{n+1}-15a_n.$$
Using the method of characteristic equations, we find that since the roots of $t^2-8t+15$ are $3$ and $5$, we have $a_n=A\cdot3^n+B\cdot 5^n$ for some $A$ and $B$. Use initial conditions to find $A$ and $B$. 
Remark: It is "better" to write the pair of recurrences $a_{n+1}=4a_n+b_n$ and $b_{n+1}=a_n+4b_n$ in matrix form, and use tools from linear algebra (eigenvalues). The solution strategy we described is in a sense more elementary, but has the disadvantage of looking like a trick. 
A: For a "not so tricky-looking way", use generating functions: Define $A(z) = \sum_{n\ge 0} a_n z^n$ and similarly $B(z)$. The recurrences:
$$
\begin{align*}
a_{n + 1} &= 4 a_n + b_n \\
b_{n + 1} &= a_n + 4 b_n
\end{align*}
$$
Also, the sequence of length 0 is bad, so $a_0 = 0$, $b_0 = 1$.
From the recurrences, by properties of generating functions:
$$
\begin{align*}
\frac{A(z) - a_0}{z} &= 4 A(z) + B(z) \\
\frac{B(z) - b_0}{z} &= A(z) + 4 B(z)
\end{align*}
$$
The solution to this linear system is:
$$
\begin{align*}
A(z) &= \frac{z}{1 - 8 z + 15 z^2}
      = \frac{1}{2} \cdot \frac{1}{1 - 5 z} 
          - \frac{1}{2} \cdot \frac{1}{1 - 3 z} \\
B(z) &= \frac{1 - 4 z}{1 - 8 z + 15 z^2}
      = \frac{1}{2} \cdot \frac{1}{1 - 5 z}
          + \frac{1}{2} \cdot \frac{1}{1 - 3 z}
\end{align*}
$$
From here you get directly:
$$
\begin{align*}
a_n &= \frac{5^n - 3^n}{2} \\
b_n &= \frac{5^n + 3^n}{2}
\end {align*}
$$
