Proving a recurrence relation for strings of characters containing an even number of $a$'s

Question

We consider strings of $n$ characters, each character being $a$, $b$, $c$, or $d$, that contain an even number of $a$'s. (Recall that $0$ is even.) Let $E_n$ be the number of such strings.

Prove that for any integer $n \ge1$,

$$E_{n+1} = 2 E_n + 4^n.$$

I tried to do induction. I got stuck.

$$\begin{align}E_{n+2} &= 2 E_{n+1} + 4^{n+1}\\ & = 2 (2E_n + 4^n) + 4^{n+1}\\ & = 4E_n + 2\cdot 4^n + 4^{n+1}\end{align}$$ Then I got lost.

Answer 1

Hint: Let $E_n$ be as in the OP, and let $O_n$ be the number of strings of length $n$ with an odd number of a's.

Then $E_{n+1}=3E_n+O_n=3E_n+(4^n-E_n)$.

Answer 2

A ''valid'' string of length $n+1$ is either a ''valid'' string of length $n$ with one of $b,c$ appended; or an ''arbitrary'' string of length $n$ with either $a$ or $d$ appended (whatever makes the parity right).