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

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.

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

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..

Originally Posted by lso

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) = ???

a(1)=20 , a (2)= 20^2 + 100 ?????

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?

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...

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."

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?!

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.