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. 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...
 A: 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).$$
A: For the first $n-1$ slots, you have $5$ choices each. For the last slot, you must fill $A$ if the first $n-1$ slots have odd number of $A$s, and anything except $A$ if there are even number of $A$s in the first $n$ slots. Let $f(n)$ be the number of ways of filling $n$ slots such that there are even number of $A$s. Then:
$$f(n)=(5^{n-1}-f(n-1))(1)+f(n-1)(4)=5^{n-1}+3f(n-1)$$
Then, expanding this recursion:
$$f(n)=5^{n-1}+3f(n-1)=5^{n-1}+3\cdot5^{n-2}+3^2f(n-2)=\cdots$$
$$f(n)=5^{n-1}+3\cdot5^{n-2}+\cdots+3^{n-1}+3^nf(0)$$
Since $f(0)=0$, we have:
$$f(n)=(5^{n-1}+3\cdot5^{n-2}+\cdots+3^{n-1})+3^n=\frac{5^n-3^n}{2}+3^n$$
$$f(n)=\frac{5^n+3^n}{2}$$
A: Well, this is embarassing.  I am going to leave a comment to the OP suggesting that she un-accept this answer and accept one of the other answers.  The answer below is wrong because I misinterpreted the question.
By converting the question into counting the number of solutions to $2x_1 + x_2 + x_3 + x_4 + x_5 = n$, I overlooked that the OP was not asking for how many possible satisfying combinations of n characters there were that used the 5 letters.  Instead, the OP was asking what are the total number of ways of permuting any satisfying combination into a $n$ character string.  That is, the OP was asking how many $n$ character words could be formed, that used the 5 characters (with A used an even # of times).
There is no simple way to convert my answer into the requested answer, because various individual solutions to $2x_1 + x_2 + x_3 + x_4 + x_5 = n$ will permit a variable number of permutations (i.e. words).  Because of this, Stars and Bars analysis, which is what I used, is totally inappropriate here.
I am going to leave this answer in, as another example of going off the rails.

There are two approaches.  One, as suggested by N. F. Taussig's comment, is:

*

*compute $c = \left\lfloor \frac{n}{2}\right\rfloor.$


*let $x_1$ range from $\{0,1,\cdots, c\}.$


*for each value of $x_1$, determine the number of solutions as a function of both $x_1$ and $n$.


*express the total number of solutions as a summation.
The alternate approach involves generating functions.
Both approaches may be viewed by delving into links that start with this.
I suspect that when the Stars and Bars problem gets this complicated, generating functions may be preferable.  Unfortunately, I don't know generating functions.  Therefore, I will map out the Stars and Bars approach.
Let $c \equiv \left\lfloor \frac{n}{2}\right\rfloor.$
For each $x_1$ in the range from $\{0, 1, \cdots, c\}$, 
let $f(x_1,n) \equiv$ the # of non-negative integer solutions to 
$x_2 + x_3 + x_4 + x_5 = (n - 2x_1).$
From Stars and Bars analysis, 
$$f(x_1,n) = \binom{[n - 2x_1] + [4-1]}{4-1} = \binom{n + 3 - 2x_1}{3}.$$
Then the overall answer will be
$$\sum_{x_1 = 0}^c f(x_1,n) ~=~ \sum_{x_1 = 0}^c \binom{n + 3 - 2x_1}{3}.$$
