How many $n$-letter words formed from $k=3$ letter classes have an even number of $a$s? Let $a$, $b$, $c$ be letters of an alphabet. How many words of $n$ letters contain an even number of a?
So I tried to do this like this:
Lets assume 'a' is the first letter. If 'a' is also the second letter we have $d_{n-2}$ words(I call the sequence d so I won't make any mistake with the letters a,b,c). If the second letter is 'b' or 'c' we have $3^{n-2}-d_{n-2}$ words, then we just need to multiply by 2 because the 2 options are symmetric.
Now lets assume the first letter is either 'b' or 'c'. There are $d_{n-1}$ words. we multiply by 2 becasue the 2 options are symmetric.
In total we got:
$d_n = 2d_{n-1}+d_{n-2}+2\cdot(3^{n-2}-d_{n-2})=2d_{n-1}+2\cdot3^{n-2}-d_{n-2}$
The goal is to find a solution without using $\sum$.
So I tried using generating functions and got:
$f(x)=2x^2\sum_{n=0}^\infty (3x)^n\sum_{n=0}^\infty (2x)^n+\sum_{n=0}^\infty (2x)^n$
Is there any way to continue from here?Am I missing something?
 A: Look at the first letter only. A string with an even number of a's starts with either:


*

*'a', followed by a string with an odd number of a's

*'b' or 'c' followed by a string with an even number of a's
Let $E_n$ be the number of strings of length $n$ with an even number of a's and $O_n$ the same but with an odd number of a's.
As lulu points out in the comments,
$$ E_n + O_n = 3^n $$
and
$$ E_n = O_{n - 1} + 2E_{n - 1} = 3^{n - 1} + E_{n - 1}$$
Now multiply both sides by $x^{n}$ and sum to get
$$ \Phi(x) = 1 + \frac{x}{1 - 3x} + x\Phi(x) $$
where $\Phi(x)$ is the generating function for $E_n$.
Hence
$$ \Phi(x) = \frac{1 - 2x}{(1 - 3x)(1 - x)}. $$
Therefore
$$ E_n = \frac{3^n + 1}{2}. $$
A: Using exponential generating functions,
$\displaystyle g_e(x)=\left(1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots\right)\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)\left(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)$
$\displaystyle\hspace{.4 in}=\frac{e^x+e^{-x}}{2}\cdot e^x\cdot e^x=\frac{1}{2}\left(e^{3x}+e^x\right)=\sum_{n=0}^{\infty}\frac{3^n+1}{2}\cdot\frac{x^n}{n!},\;\;$ so $\;\displaystyle d_n=\frac{3^n+1}{2}$.
A: Consider exactly 2 $a$'s:
There are 
${n \choose 2}$ ways to choose the two positions for the $a$s, and $2^{n-2}$ possible ways to fill the remaining $n-2$ slots with either a $b$ or a $c$, the total being ${n \choose 2} 2^{n-2}$.
Likewise for exactly 4 $a$s:
${n \choose 4}$ 
and
$2^{n-4}$,
giving ${n \choose 4} 2^{n-4}$.
And likewise for all even number of $a$s.  How many such terms are there?  $k = \lfloor n/2 \rfloor$.
So sum these up:
$\sum\limits_{i=1}^{\lfloor n/2 \rfloor} {n \choose 2 i} 2^{n-2 i}$.
