Quintary Sequences

Question

Can anyone tell the answer for this question and explain it in simplified form? Find the number of n-digit quintary sequence (sequence made up of the digits 0, 1, 2, 3, 4) that contains an even number of 1s?

Answer 1

For an $n$-digit sequence, you want to count the number of sequences that have $0, 1, 2, ... \lfloor{n/2}\rfloor$ pairs of ones.

If $m$ is the number of pairs of ones, then there are ${n \choose 2m}$ places to put them. Then, there are $4^{n-2m}$ choices for the remaining digits in the sequence.

So, the number of sequences $N(n)$ is

$$N(n) = \sum_{m=0}^{\lfloor{n/2}\rfloor}{n \choose 2m}4^{n-2m}.$$

Answer 2

As it happens, to find something we need, we must also find something we don't need. So let $a_n$ be the number of those sequences with even number of 1s, and $b_n$ the number of sequences with odd number of 1s. It is quite easy to compute $a_1$ and $b_1$ by hand. Now what happens if we append one more digit to the end of such sequence? $n$ becomes $n+1$; also, if the digit was $1$, then the sequence switches from "even" to "odd" or vice versa, and if it was any other digit, it stays where it was. So, all in all, $$\left\{\begin{align}a_{n+1}=4a_n+b_n\\ b_{n+1}=a_n+4b_n \end{align}\right.$$ Let's calculate the first few values: $$\begin{array}{l|llll} n& 1& 2& 3&\dots \\ a_n& 1& 8& 49&\dots \\ b_n& 4& 17& 76&\dots \\ \end{array}$$ Now, by finding the roots of the characteristic equation, which are obviously 3 and 5 (or, if you are not familiar with that technique, by guessing the formula and proving it by induction), we see: $$a_n={5^n-3^n\over2},\;b_n={5^n+3^n\over2}$$