Find number of legal codes containing even number of zeros

Question

A decimal code is declared legal if it has an even number of zeros$.$ For example $1900200$ is a legal code, but $10002$ is not. Let $a_n$ be the number of legal decimal codes of length $'n'$. Then

(A) $a_n=8a_{n-1}+10^{n-1}$

(B)$a_n=\frac{8^n+10^n}{2}$

(C) $a_n=9a_{n-1}+10^n$

(D)$a_n=9^n+10^n$

Answer given are the options (A) and (B)

My Attempt We can create the n digit specified code by placing any non-zero digit after unit's place in $(n-1)$ legal code. Also, we can place a zero in any one of the illegal codes.

$a_n=a_{n-1}\times 9+(10^{n-1}-a_{n-1})\times 1=8a_{n-1}+10^{n-1}$

But how to get option (B).

Is there a way independent of using above recursion.

Answer 1

There is a clever direct argument. Decimal sequences of length $n$ fall into two classes:

1. Sequences without any "0"s or "1"s. There are $8^n$ sequences of this type. All of them are valid codes.

2. Sequences with at least one "0" or "1". There are $10^n-8^n$ sequences of this type. Exactly half of them are valid codes.

Why exactly half? Consider the following function defined on the set of sequences in class $2$; find the leftmost number in the sequence which is either "0" or "1", and replace it with "1" or "0", respectively. This function has no fixed points, and is its own inverse, so it partitions the second class into pairs of sequences that are mapped to each other. In each pair, exactly one sequence has an even number of zeroes, which proves exactly half of these sequences are valid.

This proves that the number of valid sequences is $$ 8^n+\frac{10^n-8^n}{2}=\frac{8^n+10^n}{2}. $$