Solve 8c Stamp Problem with Recurrence Relation

[Punkyc7]

Use a recurrence relation to find the number of ways that stamps that have a value of 1 cent , 2 cents and a 3 cents can add up to eight cents.

How exactly do you go about solving a problem like this without writing a program to find all the possibilities?

The answer given is 81, but I have know Idea how to get it.

 

[Ray Vickson]

How would you interpret the coefficient of x^8 in the expansion of (x+x^2+x^3)^n?

RGV

 

[Punkyc7]

Would that be the number of times a certain combination happens?