Recurrence Relation Example

1. Oct 9, 2015

tamuag

1. The problem statement, all variables and given/known data
This isn't actually a homework question.Actually, it's an example from Rosen's Discrete Math and Its Applications that I'm having difficulty with:

"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 $a_n$ be the number of valid n-digit codewords. Find a recurrence relation for $a_n$."

2. Relevant equations

3. The attempt at a solution

Here's an explanation from a Stackexchange user, that more or less is identical to the explanation from the book: "Take the number of valid strings in the previous, $a_{n - 1}$, you can't add a 0 because that would make the previously valid string invalid, so you can add any digit from 1-9 (i.e. 9 digits). So right away we know that $a_n > 9a_{n - 1}$.

But what about the previously invalid strings? If it was invalid, then there were an odd number of 0's and adding one more will make it valid. Now it depends on whether or not you consider zero 0's an even number of 0's. If so just take the compliment of the valid strings: $10^{n - 1} - a_{n - 1}$. This gives:

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

My question is where does $10^{n - 1}$ come from? I would understand this example if I could get where they were getting that term from.

2. Oct 9, 2015

andrewkirk

How many possible different strings of length n-1 are there?

3. Oct 9, 2015

tamuag

$a_{n−1}$?

4. Oct 9, 2015

andrewkirk

No. $a_{n-1}$ is the number of valid strings.

5. Oct 9, 2015

tamuag

In the Stackexchange user's explanation, he says that $10^{n−1}−a_{n−1}$ is the complement of the number of valid strings. Is that to say, that the number of strings of length n-1 is $10^{n-1}$?

Last edited: Oct 9, 2015
6. Oct 9, 2015

andrewkirk

How would you go about working out the number of different possible strings of length n-1 (ignoring any notions of validity introduced in the question), where every element of the string can have any one of 10 possible values?

eg if you have a combination lock with n-1 barrels, and each barrel has the numbers 0-9, how many different possible combinations are there?

7. Oct 9, 2015

tamuag

$10^{n-1}$?

Correct me if I'm wrong: $10^{n-1}$ is the term of all bit strings of length n-1 because the first digit of that string is any of ten digits ($10$), which can each be followed by any of ten digits ($10^2$), which can each be followed be ten different digits ($10^3$), and so on ($10^{n-1}$)?