recurrence relations for computation the number of n-digit binary sequences

Question

Find a system of recurrence relations for computation the number of n-digit binary sequences with an even number of 0 and an even number of 1.

Answer 1

Let $EE(n)$ be the number of sequences of length $n$ that have an even number of each. Let $EO(n)$ be the number of sequences of length $n$ that have an even number of $0$'s and an odd number of $1$'s. Define $OE(n)$ and $OO(n)$ analogously.

We have the recurrences $$EE(n)=EO(n-1)+OE(n-1),$$ and $$EO(n)=EE(n-1)+OO(n-1)$$ and two others obtained analogously. The justifications are straightforward. For example, any sequence of length $n$ with an even number of each can be obtained by appending a $1$ to a sequence of length $n-1$ that has an even number of $0$'s and an odd number of $1$'s, or by appending a $0$ to a sequence of length $n-1$ that has an odd number of $0$'s and an even number of $1$'s.

Note that by symmetry we have $EE(n)=OO(n)$ and $EO(n)=OE(n)$, so we could have used a system with only two items instead of four. We used four in order to illustrate what we might do under less symmetric circumstances.

Remark: If you use $S(n)$ (same) and $M(n)$ (mixed) you will obtain a much simpler system. And by a little manipulation you can eliminate $M(n)$, obtaining a single recurrence for $S(n)$, the function we are really interested in.