Where Does 10^{n-1} Come From in the Recurrence Relation Example?

[tamuag]

Homework Statement

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."

Homework Equations

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.

 

[andrewkirk]

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

 

[tamuag]

a_{n−1}?

 

[andrewkirk]

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

 

[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}?

 

[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 anyone 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?

 

[tamuag]

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?

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})?