Find number of words of length $n$ which can be written using letters: $\{A,B,C,D,E\}$, but letter $A$ has to appear even number of times.
I was thinking of stars and bars method so I started this way:
$x_1+x_2+x_3+x_4+x_5=n$, where $x_i\geq 0$ and $x_1$ is an even number. I dont know if in this task $A$ can appear $0$ times since this is a question from an old test. Let's say that it can appear $0$ times. Now when I try to substitute $y_1=\frac{x_1}{2}$ and $y_i=x_i, i=2,3,4,5$, I do not know what to do with $n$ on the right side of the equation, if this is the right approach in the first place. Since these are combinations I would have to permute everything at the end…
Best Answer
We can use reccurrence relations. Let's say $a_n$, number of even numbers of times of letter $A$ with $n$ letters. Also $b_n$ number of odd numbers of times of letter $A$ with $n$ letters. Therefore for $n\geq 1$, $$a_n +b_n=5^n \tag{1}$$.
Otherhands, for $a_{n+1}$; if last letter is $A$ then number of this sub-case: $b_n$, if last letter is $B,C,D$ or $E$ then number of this sub-case: $4a_n$. Hence we yieldes for $n\geq 1$, $$ a_{n+1}=4a_n + b_n \tag{2}$$
By $(1)$ and $(2)$, we find $a_{n+1}-3a_n=5^n$. Easly we can see that $a_1=4$, $a_2=17$. By $a_{n+1}-3a_n=0$ homogen form and with term $5^n$; roots of characteristic polynom of this reccurrence relation are $3$ and $5$. That is $a_n$ will be form:
$$ a_n =C_15^n +C_23^n \tag{3}$$
By using $a_1=4$, $a_2=17$ values at $(3)$: we yields $C_1=C_2=\dfrac{1}{2}$. Therefore, $$ a_{n} = \dfrac{1}{2}(5^n + 3^n).$$