How many $n$-digit sequences of $0,1 \ \text{or} \ 2$s contain an odd numbers of $0$s? Problem : There are $3^n$ n-digit sequences in which each digit is $0$, $1$ or $2$. How many of these sequences have an odd number of $0$'s ?
Let $o(n)$ = the number of n-digit sequences which have an odd number of $0$'s and
$e(n)$ = the number of n-digit sequences which have an even number of $0$'s.
Obviously $o(n) + e(n) = 3^n$ and by examples I can see that $o(n)=e(n)-1$ but I don't know how to show this.
Moreover if we have $x$ digits to choose from then by examples I see that $o(n) = e(n) - {n}^{x-2}$. And if we consider the number of sequences which have a number congruent to $0$, $1$ respectively $2$ (modulo $3$) of $0$s we see that these numbers are in arithmetic progression.
Can someone prove these assumptions to me or disprove them if they are not right?  
 A: One way of seeing $o(n)=e(n)-1$ (which as you noted is enough to finish): Consider the following operation, which is defined on all sequences except the all $2$ sequence:
Take the first digit which is $0/1$, and switch it between $0$ and $1$.
For example, $2101$ is mapped to $2001$. Two things which you can quickly check about this map are


*

*Applying the map twice returns you to your original sequence.  So the map effectively pairs off the $3^n-1$ sequences that aren't all $2$.

*In each pair, one sequence has an even number of zeroes, the other has an odd number.
So those $3^n-1$ sequences are split evenly between even and odd.  The one left over sequence has no zeroes, so is even.  
The same argument works if you have $x$ digits to choose from, the only difference being that there are now $(x-2)^n$ sequences containing neither $0$ nor $1$ that aren't paired off.
In combinatorics, this sort of argument is referred to as a sign-reversing involution.
A: Given a string of length $n$, If the last digit is $0$ then you want to have even number of $0s$ in the first $n-1$ digits, hence $e(n-1)$. If the last digit is eigher $1$ or $2$, then you need an odd number of zeros in the first $n-1$ digits, hence $2o(n-1)$.
So we have $o(n)=2o(n-1)+e(n-1)=2o(n-1)+3^{n-1}-o(n-1)=3^{n-1}+o(n-1)$.
Multiplying both side by $x^n$ to get
$x^no(n)=x^n3^{n-1}+x^no(n-1)$ then 
$\sum_{n=1}^{\infty}x^no(n)=\sum_{n=1}^{\infty}x^n3^{n-1}+\sum_{n=1}^{\infty}x^no(n-1)$
let $F(x)=\sum_{n=0}^{\infty}x^no(n)$, then 
$F(x)-o(0)=x\sum_{n=1}^{\infty}x^{n-1}3^{n-1}+x\sum_{n=1}^{\infty}x^{n-1}o(n-1)$
$F(x)-o(0)=x\sum_{n=1}^{\infty}(3x)^{n-1}+xF(x)$
$F(x)(1-x)=x\sum_{n=1}^{\infty}(3x)^{n-1}$
$F(x)=\frac{x}{1-x}\sum_{n=1}^{\infty}(3x)^{n-1}$
$F(x)=\frac{x}{1-x}\frac{1}{1-3x}$
$F(x)=(\frac{-1}{2}+\frac{3^n}{2})\sum_{n=0}^{\infty}x^n$
so $o(n)=(\frac{3^n-1}{2})$
A: Assume that $n$ is odd, $n = 2s+1$
Note that number of $n$-digit sequences with $k$ number of zeroes is ${N_k}(n) =$ $n \choose k$$2^{n-k}$.
Thus, $$o(n) = \sum_{m=0}^s{N_{2m+1}}(n) = \sum_{m=0}^s{n \choose 2m+1}{2^{n-2m-1}} = \sum_{m=0}^s{n \choose 2m+1}{1^{2m+1} 2^{n-2m-1}} \\ = \frac{(2+1)^n-(2-1)^n}{2} = \frac{3^n-1}{2}$$
If $n$ is even, let $n = 2t$. Then $o(n) = \sum_{m=0}^{t-1}{n \choose 2m+1}{2^{n-2m-1}} = \frac{3^n-1}{2}$, and you are done.
Moreover, $$o(n-1) = \frac{3^{n-1}-1}{2} \implies \fbox{$o(n-1) + 3^{n-1} = o(n)$}$$
Similarly, for $e(n)$, $$e(n)=\begin{cases}{\sum_{m=0}^s{n \choose 2m}{2^{n-2m}}}&n=2s+1 \\ \sum_{m=0}^t{n \choose 2m}{2^{n-2m}}& n = 2t\end{cases}$$
Thus, $$e(n) = \frac{(2+1)^n+(2-1)^n}{2} = \frac{3^n+1}{2}$$
Now, by further computation, one can find out that $\fbox{$e(n)-o(n) = 1$}$.
A: You can use exponential generating functions to solve this problem too.
Let $f(n)$ be the number of ternary sequences of length $n$ with an odd number of zeroes and let $F(z)=\sum_{n=0}^\infty f(n)\frac{z^n}{n!}$ be the associated exponential generating function. Then
$$
\begin{align*}
\left(z+\frac{z^3}{3!}+\frac{z^5}{5!}+\dotsb\right)\left(1+z+\frac{z^2}{2!}+\dotsb\right)^2
&=\sum_{n=0}^\infty\left(\sum_{k_1+k_2+k_3=n\; k_1\, \text{odd}, k_2, k_3\geq 0}\frac{n!}{k_1!k_2! k_3!}\right)\frac{z^n}{n!}\\
&=\sum_{n=0}^\infty f(n)\frac{z^n}{n!}
\end{align*}
$$
i.e. we have that
$$
F(z)=e^{2z}\times\frac{e^z-e^{-z}}{2}=\frac{e^{3z}-e^{z}}{2}=\sum_{n=0}^\infty \frac{3^n-1}{2}\frac{z^n}{n!}
$$
whence
$$
f(n)=\frac{3^n-1}{2}\quad (n\geq 0).
$$
