Given an alphabet with three letters a, b, c. Find the number of words of n letters which contain an even number of a's. 
Given an alphabet with three letters $a$, $b$ and $c$. Find the number of words of n letters which contain an even number of $a$'s.

I tried to make cases and then do it; but this would take forever and then there would be the issue of simplification of the answer. Therefore, I think this would require a more clever thinking than the traditional brute force.
 A: Another way to solve this problem is to let $F(x) = (2 + x)^n$, and notice that coefficient of $x^m$ is the number of words with $m$ 'a's. Next you can use the fact that $\frac{1}{2} ((-1)^{n} + (1)^{n})$ is equal to one if $n$ is even and zero if $n$ is odd to filter out the odd words. Doing this we determine that the answer is $\frac{1}{2} (F(1) + F(-1)) = \frac{1}{2}(3^{n} + 1)$.
A: Use reccurence relations:
Let $E_n$ be the number of words with length $n$ and even number of $a$'s. And $O_n$ be the number of words with length $n$ and odd number of $a$'s.
Take any word from length $n$. To find $E_n$ take a look a the last letter. If it's $b$ or $c$ then there are $E_{n-1}$ ways to choose the first $n-1$ letters. On the other side if it's $a$ there are $O_{n-1}$ ways to choose the first $n-1$ letters. Therefore:
$$E_n = 2E_{n-1} + O_{n-1}$$
Now using this and the fact that $O_n + E_n = 3^n$ we have that:
$$E_n = E_{n-1} + 3^{n-1}$$
Now solving this reccurence relations will give you the form of $E_n$.

One way to solve it is:
$$E_n - 3E_{n-1} = E_{n-1} + 3^{n-1} - 3E_{n-2} - 3^{n-1} \implies E_n = 4E_{n-1} - 3E_{n-2}$$
The characteristic equation of this reccurence relation is: $x^2 - 4x + 3 = 0$, whose solutions are $x_1 = 3, x_2 = 1$.
Therefore we have that $E_n = A\cdot 3^n + B \cdot 1^n$
As $E_1 = 2, E_2 = 5$ we have that:
$$\begin{cases} 2 = 3A + B \\ 5 = 9A + B \end{cases}$$
Solving this system of linear equations we have that $A=B=\frac 12$. Therefore:
$$\boxed{ E_n = \frac{3^n + 1}{2}}$$
