<s>[INST] 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?

 [/INST] 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*}
$$
</s>