Results 1 to 11 of 11

Math Help - how express the solution of this counting problem in term of a difference equation?

  1. #1
    lso
    lso is offline
    Newbie
    Joined
    Dec 2010
    Posts
    8

    how express the solution of this counting problem in term of a difference equation?

    the jukebox at the pub charges $1 to play a pop song and $o.50 to play a rock song. it it offers a selection of 20 pop songs and 100 rock songs, how many different sequences of songs can i choose to listen if i have n50cents ( assume I am happy to listen to any given song multiple times). ?!

    after that i should find an explicit solution using a generating function
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Let a(n) be the number of song sequences you can listen to with 50n cents; you want to find a recurrence for a(n).

    How many song sequences can you listen to if n=1?

    If you knew how to find a(1), a(2), .... , a(n), how could you compute a(n+1)?
    It may help to consider two cases: (1) the n+1st song is a pop song; (2) the n+1st song is a rock song.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    lso
    lso is offline
    Newbie
    Joined
    Dec 2010
    Posts
    8
    i found that the sequence is 0,1,2,2,3,3,4,4,5,5,6,6,..........

    and i thought it might be express in terms of DE as U(n+2)=U(n+1)+Un-U(n-1) but not really sure at all, and starting from here it looks hard to find the generating function
    Follow Math Help Forum on Facebook and Google+

  4. #4
    lso
    lso is offline
    Newbie
    Joined
    Dec 2010
    Posts
    8
    but doing what i have just done I completely ignored the fact that there are 20 pop songs and 100 rock ones , so, again, don't know..
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by lso View Post
    i found that the sequence is 0,1,2,2,3,3,4,4,5,5,6,6,..........

    and i thought it might be express in terms of DE as U(n+2)=U(n+1)+Un-U(n-1) but not really sure at all, and starting from here it looks hard to find the generating function
    If you had ony 0.50, you could listen to any rock song. So a(1) = ???
    Follow Math Help Forum on Facebook and Google+

  6. #6
    lso
    lso is offline
    Newbie
    Joined
    Dec 2010
    Posts
    8
    a(1)=20 , a (2)= 20^2 + 100 ?????
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Since there are 100 rock songs, a(1) = 100.

    For $1.00 (n=2), you can listen to any two rock songs or any one pop song. So how many sequences is that?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    lso
    lso is offline
    Newbie
    Joined
    Dec 2010
    Posts
    8
    a(1) = 100
    a(2)= 100^2 + 20
    a(3)= 100^3 + 20 x 100
    a(4)= 100^4 + 20 x (100^2 + 20 )
    a(5)= 100^5 + 20 x (100^3 + 20 x100)


    it looks like the DE is Un = 100^n + 20 U(n-2)

    but trying to solve this and get the generating functions is extremely hard.. so it might not be the solution at all ...confused...
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    I agree with you on a(1) and a(2), but I don't think you have a(3) correct. In the n=3 case you can buy three rock songs or one pop song and one rock song. If you buy three rock songs, there are 100^3 possible sequences. But if you buy 1 pop song and one rock song, they can be ordered as PR or RP, so there are 2 * 20 * 100 possibilities.

    Think about my previous recommendation:
    "If you knew how to find a(1), a(2), .... , a(n), how could you compute a(n+1)?
    It may help to consider two cases: (1) the n+1st song is a pop song; (2) the n+1st song is a rock song."
    Follow Math Help Forum on Facebook and Google+

  10. #10
    lso
    lso is offline
    Newbie
    Joined
    Dec 2010
    Posts
    8
    so i found that a(1)=100
    a(2)=100^2 +20
    a(3)=100^3+(2x20x100)
    a(4)=100^4+(3x20x100^2)+20^2
    a(5)=100^5+(4x20x100^3)+(3x20^2x100)

    so the pattern is Un= 100Un-1 +20Un-2

    now it is homogeneous, Horrible to solve but at leadt homogeneous...is it correct?!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Yes, that's right.

    However, you should be able to explain your recurrence without looking for a pattern in the first few values.

    Suppose you have 50n cents. If the last CD you buy is a rock song, for which there are 100 choices, then you had 50(n-1) cents to buy the previous CDs, which could be done in Un-1 ways. If the last CD you buy is a pop song, for which there are 20 choices, then you had 50(n-2) cents to buy the previous CDs, which could be done in Un-2 ways. Putting it all together, you get the recurrence.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Trying to express a solution as a series
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: April 30th 2010, 09:18 AM
  2. Express the term in roots and powers
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 6th 2009, 12:38 AM
  3. Replies: 3
    Last Post: February 21st 2009, 06:01 AM
  4. Replies: 2
    Last Post: April 5th 2008, 05:57 PM
  5. Replies: 1
    Last Post: March 31st 2008, 06:53 AM

Search Tags


/mathhelpforum @mathhelpforum