How many strings of length $n$... Let $n$ be a positive integer. If each $a_i$ is chosen from $\left\{ 0,1,2, \dots, 9 \right\},\;$ $1\leq i\leq n$, then how many strings of length $n$ ($a_1a_2\dots a_n$) are there such that the number of occurrences of $0$ is even? Thanks!
 A: Let us fix the alphabet as $\{0, 1, 2, \dots, M\}$ (we'll later take $M = n$). Let $a_n$ be the number of strings of length $n$ which contain an even number of $0$s, and $b_n$ be the number of strings of length $n$ which contain an odd number of $0$s. Note that there are $(M+1)^n$ strings of length $n$ over that alphabet, so $a_n + b_n = (M+1)^n$. For $n = 0$, we can see that $a_0 = 1$ (the empty string) and $b_0 = 0$.
We can write down recurrence relations for $a_n$ and $b_n$. If we consider how we can get a string of length $n+1$ by appending a symbol (either $0$ or one of $1, \dots, M$) to a string of length $n$, we can see that:
$$\begin{align}
a_{n+1} &= Ma_n + b_n\\
b_{n+1} &= a_n + Mba_n
\end{align}$$
Writing $X_n = \pmatrix{a_n \\ b_n}$, this means 
$$\begin{align}
X_0 &= \pmatrix{1 \\ 0} \\
X_{n+1} &= \pmatrix{M & 1 \\ 1 & M}X_n
\end{align}$$
Calling the matrix $T = \pmatrix{M & 1 \\ 1 & M}$, this means $X_n = T^nX_0$. You can verify that
$$T^n = \frac12 \pmatrix{(M-1)^n+(M+1)^n & (M+1)^n-(M-1)^n \\ (M+1)^n-(M-1)^n & (M-1)^n+(M+1)^n}$$
which gives $\pmatrix{a_n \\ b_n} = X_n = T^nX_0 = T^n\pmatrix{1 \\ 0} = \frac12 \pmatrix{(M-1)^n+(M+1)^n \\ (M+1)^n-(M-1)^n}$ and in particular $$a_n = \frac{(M-1)^n+(M+1)^n}{2}$$ or when $M = n$, $$a_n = \frac{(n-1)^n+(n+1)^n}{2}.$$

Alternatively, as $b_n = (M+1)^n - a_n$, the recurrence $a_{n+1} = Ma_n + b_n$ is the same as $a_{n+1} = Ma_n + ((M+1)^n - a_n) = (M-1)a_n + (M+1)^n$. Here, letting $c_n = 2a_n - (M+1)^n$, note that the recurrence becomes:
$$\begin{align}
a_{n+1} &= (M-1)a_n + (M+1)^n \\
2a_{n+1} - (M+1)^{n+1} 
 &= 2(M-1)a_n + 2(M+1)^n - (M+1)^{n+1} \\
 &= 2(M-1)a_n + (M+1)^n(2 - (M+1)) \\
 &= 2(M-1)a_n - (M+1)^n(M-1) \\
 &= (M-1)(2a_n - (M+1)^n) \\
c_{n+1} &= (M-1)c_n
\end{align}$$
and $c_0 = 2a_0 - 1 = 2 - 1 = 1$, so $c_n = (M-1)^n$, which gives 
$a_n = ((M-1)^n + (M+1)^n)/2$ as before.

Of course, there is also probably an easy combinatorial proof showing why $a_n = ((n-1)^n+(n+1)^n)/2$; I can't think of one right now.
