Proving strings We consider strings of n characters, each character being a, b, c, or d, that
contain an even number of as. (0 is even.) Let $E_n$ be the number of such strings.Prove that for any integer  $n  \geq1$,E_(n+1) =2 * $E_n$ + $4^n$
 A: We are going to count the number of strings of length $n+1$ with an even number of a's. First, take a look at the first $n$ characters. If the number of a's is odd, the last character must be an $a$. That gives $4^n-E_n$ possibilities. If the number of a's in the first $n$ digits is even, we know that the number of possibilities for those first $n$ characters is $E_n$. The last character must not be an a, since then the total number of $a$'s would be odd. Thus, there are three possible choices for character $n+1$. Together, this yields
$$
E_{n+1}=4^n+2E_n
$$
A: As this is looking a bit homeworky I will not give you the answer directly.
Observation 1: A sequence in $E_{n+1}$ can be obtained in exactly one of the two ways: 1) from a sequence in $E_n$ and by adding $b,c$ or $d$. Or, 2) by a sequence on $n$ characters which is not in $E_n$ and adding an $a$ to make it valid. 
Observation 2: The total elements of $E_{n+1}$ is the sum of 1) and 2). The number of ways to form a sequence from 1) should be straightforward. But what about 2)? Remember that $E_n + \text{sum of invalid sequences} = 4^n$.
Now do the math :-)
