- #1
tamuag
- 9
- 0
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 [itex]a_n[/itex] be the number of valid n-digit codewords. Find a recurrence relation for [itex]a_n[/itex]."
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, [itex]a_{n - 1}[/itex], 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 [itex]a_n > 9a_{n - 1}[/itex].
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: [itex]10^{n - 1} - a_{n - 1}[/itex]. This gives:
[itex]a_n = 9a_{n - 1} + 10^{n - 1} - a_{n - 1} = 8a_{n-1} + 10^{n - 1}[/itex]"
My question is where does [itex]10^{n - 1}[/itex] come from? I would understand this example if I could get where they were getting that term from.