Forming n-letter words from letters ABCDEF I have a real discrete structure problem :/
Suppose you have letters ABCDEF, how many n-letter words can be formed such that the frequency of A is an odd number? The letters can be repeated.
Can somebody tell me how to solve this?
 A: Let $o(n)$ be the number of such words of length $n$ with an odd number of $A$’s. We can build these words by choosing an odd $k\in\{0,1,\ldots,n\}$, picking $k$ positions in the word for $A$’s, and filling the other $n-k$ positions with letters from the set $\{B,C,D,E,F\}$; given $k$, this can be done in $\binom{n}k5^{n-k}$ ways, so
$$o(n)=\sum_{{k=0}\atop{k\text{ odd}}}^n\binom{n}k5^{n-k}\;.$$
Let $e(n)$ be the number of words of length $n$ with an even number of $A$’s; clearly 
$$e(n)=\sum_{{k=0}\atop{k\text{ even}}}^n\binom{n}k5^{n-k}\;.$$
There are $6^n$ words of length $n$, so $$e(n)+o(n)=6^n\;.\tag{1}$$ On the other hand,
$$\begin{align*}
e(n)-o(n)&=\sum_{{k=0}\atop{k\text{ even}}}^n\binom{n}k5^{n-k}-\sum_{{k=0}\atop{k\text{ odd}}}^n\binom{n}k5^{n-k}\\\\
&=\sum_{k=0}^n\binom{n}k(-1)^k5^{n-k}\\\\
&=(-1+5)^n\\\\
&=4^n\;.
\end{align*}\tag{2}$$
Combine $(1)$ and $(2)$ to solve for $o(n)$ and $e(n)$.
Added: You can also approach it by finding a recurrence and solving it for a closed form. Let $O_n$ be the set of words of length $n$ with an odd number of $A$’s, and let $E_n$ be the set of words of length $n$ with an even number of $A$’s. Let $w\in O_n$, let $w_f$ and $w_\ell$ be respectively the first and last letters of $w$, and let $w'$ be the word of length $n-2$ obtained by deleting $w_f$ and $w_\ell$ from $w$. If exactly one of $w_f$ and $w_\ell$ is an $A$, then $w'\in E_{n-2}$; otherwise, $w'\in O_{n-2}$. Conversely, any $w'\in E_{n-2}$ can be extended to a word in $O_n$ in $10$ ways by adding an $A$ at one end and a non-$A$ at the other, and any $w'\in O_{n-2}$ can be extended to a word in $O_n$ in $26$ ways by appending an $A$ at each end or a non-$A$ at each end. It follows that 
$$\begin{align*}
o(n)&=10e(n-2)+26o(n-2)\\
&=10\big(o(n-2)+e(n-2)\big)+16o(n-2)\\
&=10\cdot6^{n-2}+16o(n-2)\;.
\end{align*}$$
This recurrence can be solved by a variety of techniques.
A: Hint: If the frequency of $A$ is an odd number that implies $A$ must appear in the word at least once.  
Now let $f_i$ be the total $n$-letter words possible that contains exactly $i$ number of $A$'s.
So the total number of $n$-letter words with an odd number of $A$'s would be:
$$f_1+f_3+\cdots+f_n,\text{ if $n$ is odd}$$
$$f_1+f_3+\cdots+f_{n-1},\text{ if $n$ is even}$$
