TITLE: Proving a recurrence relation for strings of characters containing an even number of $a$'s
QUESTION [4 upvotes]: 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.

REPLY [1 votes]: 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)$.

REPLY [0 votes]: 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).
{"set_name": "stack_exchange", "score": 4, "question_id": 665118}