Results 1 to 2 of 2

Math Help - Please Help! Recurrence Problem!

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    1

    Please Help! Recurrence Problem!

    2. Consider the following situation: you need to tile a walkway with tiles of three colors (red, green, and black). The one rule that must be obeyed is that you may never have consecutive red tiles. Let an represent the number of different patterns for an n-tile walkway.

    A. Find a recurrence relation (donít forget initial conditions) for the sequence an. Be certain to explain why it applies.

    B. Use the generating functions method developed in class to find an
    explicit formula for the a sequence.

    can anyone help? I have no idea how to even start.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member arpitagarwal82's Avatar
    Joined
    Feb 2009
    Posts
    103
    This is what came in y mind.

    Consider an as sequence of n tiles.

    There can be two case. nth tile is red or nth tile is not red.

    Case I nth tile is red.
    In that can for an+1 there can be either green tile or black tile in n+1 position. there cant be erd tile (as no consecutive red tile).
    So an+1 = an +2 --------- eq1

    Now n+1 tile is not red. so n+2 tile can be either of tree color.
    so an+2 = an+1 + 3 ---------eq2

    adding eq1 and eq2
    an+2 = an +5



    Case II
    nth tile is not red
    so n+1 tile can be either of 3.
    so an+1 = an +3 ---eq3

    And the case where n+1 tile is red,
    an+2 = an+1 +2 ------eq4

    adding eq3 and eq4

    an+2 = an+5

    ----------------------------------------------------------

    So in both the case we are getting recuursive relation as

    an+2 = an+5 Answer.


    I need to think more over this.
    let m know if you feel answer is wrong. We can discuss the problem further.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recurrence relation problem!
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 9th 2011, 04:54 PM
  2. Recurrence Relation Problem...
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 10th 2010, 02:41 PM
  3. Recurrence problem
    Posted in the Calculators Forum
    Replies: 2
    Last Post: November 24th 2009, 01:53 AM
  4. recurrence problem...
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: August 20th 2009, 05:43 PM
  5. Recurrence Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 15th 2006, 05:10 AM

Search Tags


/mathhelpforum @mathhelpforum