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

  1. Dec 4, 2013 #1
    I boxed the portion of the solution that I am questioning.

    How come the number of invalid strings is only 3n-1 - an-1 and not
    3(3n-1 - an-1) ?

    As you can see there are three cases (Which are to the right of the black box)

    In all the three cases, the portion boxed in red is a string of length n-1 and does not have any consecutive numbers

    Case 1:
    The first number is a 1, then the second number must also be a 1
    so that the string has a pair of consecutive numbers

    Case 2
    The first number is a 2, then the second number must also be a 2
    so that the string has a pair of consecutive numbers

    Case 3
    The first number is a 0, then the second number must also be a 0
    so that the string has a pair of consecutive numbers
     

    Attached Files:

  2. jcsd
  3. Dec 5, 2013 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    This is not true. There is no requirement that the "pair of consecutive numbers" be the first two. For example, 100 is a valid string with n= 3.
     
  4. Dec 5, 2013 #3
    The string of length n has the requirment that it must have a pair of consecutive numbers, so if the 2nd term through the nth term of the string don't have a pair of consecutive numbers then the first term and second term must be the same inorder to satisfy the requirement.
     
  5. Dec 6, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I don't understand your logic. The reasoning in the attachment starts with an invalid string length n-1. By definition there are an-1 valid strings of that length, and obviously there are 3n-1 total strings of that length. Therefore there are (3n-1 - an-1) invalid strings length n-1. For each such invalid string, there is exactly one way of tacking on an nth (at the given end) to produce a valid string length n.
    If that doesn't help, I'll need you to spell out your own reasoning more clearly.
     
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
  1. Recurrence Relation (Replies: 1)

Loading...