I write down a string of $k$ letters, where each letter is $X, Y, \text{or } Z.$ The letter $X$ appears an even number of times. How many different sequences of letters could I have written down?
I think I need to start by setting up some cases, and building a recursion from that. I tried but arrived at a really weird form. May I have a start, please?
On
Note: The other "solutions" here allow $0$ $X$s in a sequence, but the OP writes: "The letter $X$ appears an even amount of times." If no $X$ appears, it is incorrect to say "$X$ appears an even amount of times." For this reason, the other approaches are incorrect, even if they given a simple solution.
Here's the correct solution:
Let $r$ be an indicator for the number of $X$s: specifically, there are $2 r$ (an even number) of $X$s. (Of course, $r = 1 \to \lfloor k/2 \rfloor$.) For a given $r$, the number of ways you can choose those $X$s is: ${k \choose 2 r}$. For each such choice, there remain $k - 2 r$ slots to be filled with $Y$s and $Z$s. For $i$ $Y$s in these slots, there are ${k - 2 r \choose i}$ ways to choose those $Y$s. (The remaining slots must be $Z$s.) You must sum for each possible value of $i$, where $i = 0 \to k - 2 r$.
Putting this together, the number of ways for this is given by the sum below in the parentheses.
Now you must sum over all possible values of $r$, i.e., from $r = 1 \to \lfloor k/2 \rfloor$.
$$\sum\limits_{r=1}^{\lfloor k/2 \rfloor} \left( {k \choose 2 r} \sum\limits_{i=0}^{k - 2 r} {k - 2 r \choose i} \right) =$$
$$-2^{-2 \left\lfloor \frac{k}{2}\right\rfloor +k-2} \binom{k}{2 \left(\left\lfloor \frac{k}{2}\right\rfloor +1\right)} \, _3F_2\left(1,-\frac{k}{2}+\left\lfloor \frac{k}{2}\right\rfloor +1,-\frac{k}{2}+\left\lfloor \frac{k}{2}\right\rfloor +\frac{3}{2};\left\lfloor \frac{k}{2}\right\rfloor +\frac{3}{2},\left\lfloor \frac{k}{2}\right\rfloor +2;\frac{1}{4}\right)-2^k+\frac{3^k}{2}+\frac{1}{2})$$
where $F$ is the hypergeometric function.
On
(The purpose of this post is to show that the two different approaches in the other answers do in fact give the same answer.)
With alphabet $\{X,Y,Z \}$ let $A_k$ be the number of length-$k$ words with evenly many $X$s. As in the answer by @david-g-stork, each such word can be constructed by first choosing where to place the $X$s -- there are $\binom{k}{2r}$ choices, with $r=0..{\lfloor k/2 \rfloor}$ (we include $r=0$ to allow words with no $X$s at all) -- then for each choice writing a sequence of only $Y$s and $Z$s in the remaining $k-2r$ places -- there are $2^{k-2r}$ such sequences -- giving $$A_k = \sum\limits_{r=0}^{\lfloor k/2 \rfloor} {k \choose 2 r} 2^{k-2r}.$$ Now, by the Binomial Theorem: $$\begin{align}\binom k0 + \binom k1 x + \binom k2 x^2 + \dots& + \binom{k}{k-1}x^{k-1} + \binom kk x^k = (1 + x)^k\\[2ex] \binom k0 + \binom k1 (-x) + \binom k2 (-x)^2 + \dots& + \binom{k}{k-1}(-x)^{k-1} + \binom kk (-x)^k = (1 - x)^k\end{align}$$ so, adding these and dividing by $2$ (noting that the odd terms cancel): $$\sum\limits_{r=0}^{\lfloor k/2 \rfloor} {k \choose 2 r} x^{2r}=\frac{(1+x)^k+(1-x)^k}{2}.$$ Therefore, $$\sum\limits_{r=0}^{\lfloor k/2 \rfloor} {k \choose 2 r} \left (\frac{1}{2}\right)^{2r}=\frac{\left (\frac{3}{2}\right)^k+\left (\frac{1}{2}\right)^k}{2}$$ and finally $$A_k = \sum\limits_{r=0}^{\lfloor k/2 \rfloor} {k \choose 2 r} 2^{k-2r}=\frac{3^k+1}{2}$$ which is the answer @tkf obtained by a recurrence relation.
NB: Alternatively, we can consider the two answers as providing a combinatorial proof of the identity $$\sum\limits_{r=0}^{\lfloor k/2 \rfloor} {k \choose 2 r} 2^{k-2r}=\frac{3^k+1}{2}.$$
Let $A_k$ denote the number of sequences of length $k$ with an even number of $X$'s.
For any of the $3^{k-1}$ sequences of length $k-1$, by adding either an $X$ or a $Y$ to the end, you may obtain a sequence with an even number of $X$'s.
Additionally, for each of the $A_{k-1}$ sequences of length $k-1$ with an even number of $X$'s, you may add a $Z$ to the end, to obtain a sequence of length $k$ with an even number of $X$'s.
Thus $A_{k}=3^{k-1}+A_{k-1}$. As $A_0=1$ we have$$A_k=1+1+3+9+\cdots+3^{k-1}=\frac{3^k+1}2.$$