1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurrence Relation Example

  1. Oct 9, 2015 #1
    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 [itex]a_n[/itex] be the number of valid n-digit codewords. Find a recurrence relation for [itex]a_n[/itex]."

    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, [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.
     
  2. jcsd
  3. Oct 9, 2015 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    How many possible different strings of length n-1 are there?
     
  4. Oct 9, 2015 #3
    [itex]a_{n−1}[/itex]?
     
  5. Oct 9, 2015 #4

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No. ##a_{n-1}## is the number of valid strings.
     
  6. Oct 9, 2015 #5
    In the Stackexchange user's explanation, he says that [itex]10^{n−1}−a_{n−1}[/itex] is the complement of the number of valid strings. Is that to say, that the number of strings of length n-1 is [itex]10^{n-1}[/itex]?
     
    Last edited: Oct 9, 2015
  7. Oct 9, 2015 #6

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  8. Oct 9, 2015 #7
    [itex]10^{n-1}[/itex]?

    Correct me if I'm wrong: [itex]10^{n-1}[/itex] is the term of all bit strings of length n-1 because the first digit of that string is any of ten digits ([itex]10[/itex]), which can each be followed by any of ten digits ([itex]10^2[/itex]), which can each be followed be ten different digits ([itex]10^3[/itex]), and so on ([itex]10^{n-1}[/itex])?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Recurrence Relation Example
Loading...