rosen example

Question

Codeword Enumeration:- A computer system considers a string of decimal digits a valid
codeword if it contains an even number of 0 digits. For instance, 1230407869 is valid,
whereas 120987045608 is not valid. Let an be the number of valid n-digit codewords. Find
a recurrence relation for an.

Answer 1

Note that $a_{1} = 9$ because there are 10 one-digit strings, and only one, namely, the string 0, which is not valid.

Then, a valid string of n digits can be obtained by appending a valid string of n − 1 digits with a digit other than 0. So, $9a_{n-1}$

Also, a valid string of n digits can be obtained by appending a 0 to a string of length n − 1 that is not valid. i.e. $10^{n-1} - a_{n-1}$

Summing these two cases, we find:

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

$= 8a_{n-1} + 10^{n-1}$