Results 1 to 13 of 13

Math Help - Difference equation

  1. #1
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28

    Difference equation

    Hi, I have a problem with below exercise:
    Express the solution to each of the following counting problems in terms of a difference equation, then use a generating function to solve the difference equation to give an explicit solution.
    I am making a border for the front of a garden bed out of small bricks that are 10 cm long and larger bricks that are 20 cm long. If the small bricks come in two colours, and the larger bricks come in three possible colours, how many different borders of length 10n cm can I make?
    Thanks in advance
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Here is how you would set up the recurrence:

    To layout a garden with 10n cm, we can use any 2 of the 10 cm blocks, and layout the rest of the 10(n-1) cm.
    Or we can use any 3 of the 20 cm blocks, and layout the rest of the 10(n-2) cm.

    a_n = 2a_{n-1} + 3a_{n-2}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28
    Thanks, this bit I understand, but have you got idea for further steps?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    This is a standard linear recurrence.
    You can rewrite it in this form: a_n - 2a_{n-1} - 3a_{n-2} = 0
    Have you learned about generating functions in class?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28
    Well, does it mean that the generating function is of the form \sum_{i=0}a_{i}x^i ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by Gibo View Post
    Well, does it mean that the generating function is of the form \sum_{i=0}a_{i}x^i ?
    Sure. Multiply the recurrence by x^n, then do a summation.

    Also, this may help: http://brooks-pdx.pbworks.com/f/CS340-Section5.4.pdf
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28
    Ok, thanks, and just the last thing. What about the initial conditions? a_{0}=1, a_{2}=2 ? Am I right
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by Gibo View Post
    Ok, thanks, and just the last thing. What about the initial conditions? a_{0}=1, a_{2}=2 ? Am I right
    a_0 = number of ways to tile 0 cm. This is 1, correct.
    a_2 = number of ways to tile 20 cm. Why is it 2?
    Also, what happened to a_1?

    You only need 2 initial conditions.
    Either pick a_0,a_1 or a_1,a_2.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28
    Well, a_{2}=2, because we can tile 20 cm in two different ways. We can use two 10cm bricks or one 20cm long. In that case a_{1}=1, is that correct?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by Gibo View Post
    Well, a_{2}=2, because we can tile 20 cm in two different ways. We can use two 10cm bricks or one 20cm long. In that case a_{1}=1, is that correct?
    What about colors?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28
    I hope now I understand a_{0}=1, a_{1}=2, hence a_{2}=7. Is that correct?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Quote Originally Posted by Gibo View Post
    I hope now I understand a_{0}=1, a_{1}=2, hence a_{2}=7. Is that correct?
    Yup
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Sep 2010
    From
    London
    Posts
    28
    Thanks a lot for being so patient. Regards Gibo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Difference equation
    Posted in the Differential Equations Forum
    Replies: 3
    Last Post: April 25th 2011, 06:43 AM
  2. difference equation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 17th 2009, 12:56 PM
  3. difference equation
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 5th 2009, 01:21 PM
  4. Difference equation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 23rd 2008, 11:12 AM
  5. difference equation
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 15th 2006, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum