Calculate the number of different words, where $0$ appears an even number of times. Let the set of words with an even length $n$ from the alphabet: $\{ 0,1,2\}$.
Calculate the number of different words, where $0$ appears an even number of times.
For example, for $n=6$ , the words $121212,001212,000000$ are allowed,but the word $100011$ is not allowed.
My idea is:
$$\sum_{k=0}^{\frac{n-2}{2}} \binom{n}{2k} \cdot \binom{n-2k}{2}$$
Is this correct?
 A: We define the two following functions: o(n)= number of words with $n$ letters where there is an odd number of $0$'s. $e(n)$=number of words with $n$ letters where there is an even number of $0$'s. It is clear $o(n)+e(n)=3^n$.We also know  $e(n+1)=2e(n)+o(n)=3^n+e(n).$ 
Let us look at the first few values of $e(n):2,5,14,41,122$
$e(1)=2=1+(1)$
$e(2)=5=1+(1+3)$
$e(3)=14=1+(1+3+9)$
$e(4)=41=1+(1+3+9+27)$
So in general we have $e(n)=1+\sum_{i=0}^{n-1}3^i$ which using the formula for geometric sum gives us $e(n)=\frac{3^n-1}{2}+1$
A: I want to say that your formula should be $\sum_{k\ge 0}\binom{n}{2k}2^{n-2k}$ because once you've chosen $2k$ positions out of $n$ for placing $0$'s in one of the $\binom{n}{2k}$ in the rest of the $(n-2k)$ places, at each place you can put a $1$ or a $2$ in $2$ ways which gives you a total of $2^{n-2k}$ ways. 
In general if you have an alphabet of size $l$ and you want the number of $n$ length words that have only even number of a particular alphabet (like $0$ here) then using the same logic that was used to get your answer, you get the number as $$\sum_{j=0}^{\lfloor n/2\rfloor}\binom{n}{2k}(l-1)^{n-2k}=\binom{n}{0}(l-1)^{n}+\binom{n}{2}(l-1)^{n-2}+\cdots+\binom{n}{2\lfloor n/2\rfloor}(l-1)^{n-2\lfloor n/2\rfloor}$$ Now, $$l^n=\binom{n}{0}(l-1)^n+\binom{n}{1}(l-1)^{n-1}+\cdots+\binom{n}{n}\\ (l-2)^n=\binom{n}{0}(l-1)^n-\binom{n}{1}(l-1)^{n-1}+\cdots+(-1)^n\binom{n}{n}\\ $$ So the desired number is $$\frac{l^n+(l-2)^n}{2}$$
A: Another cool way is by using Generating functions. If you write the automata that accepts that kind of String and use the Schützenberger theorem, you can come up with it easily. i.e. 
$\frac{1-5x^2}{1-10x^2+9x^4}$ And from them, you got the following recursion
$a_0=1,a_1=0,a_2=5,a_3=0$
$a_n=10a_{n-2}-9a_{n-4}$ for $n\geq4$.
A: Another way is by using exponential generating function:
Since $0$ appears even number of times and $1,2$ has no restriction, the  egf is:
\begin{align*}
  G(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)^2 \\
  &= \left(\frac{e^x+e^{-x}}{2}\right)e^{2x} \\
  &= \frac{e^{3x}+e^{x}}{2}
\end{align*}
and $$\left[\frac{x^n}{n!}\right]G(x) = \frac{3^n+1}{2}$$
A: The recurrence relation for this problem will be
$$A_n = A_{n-1} + 3^{n-1} ; n>1 $$
$$A_1 = 2$$
Solve this recurrence equation using homogeneous and particular solution method.
You will get the answer: $$(3^n + 1)/2$$
