Recursion (homework) Problem

[chiachu]

It isnt probabilty, but i was hoping you guys could help me out. Im trying to study for a midterm i have in a few days, and this problem has me completely stumped:

Suppose we have 10 cent stamps, 18 cent stamps and 28 cent stamps, each in unlimited suppply. Let f(n) be the number of ways of obtaining 'n' cents of postage if the order in which we put on stamps counts. For example, f(10) = 1 and f(20) = 1 (two 10 cent stamps), while f(28) = 3 (one 28 cent stamp, or a 10 cent stamp followed by and 18 cent, or a 18 cent stamp followed by a 10 cent).

If n > 29, derive a recurrance for f(n)

Thanks in advance for any help.

[uphigh_downlow]

From a quick look, it seems like

F(n) = F(n-10) +F(n-18) +F(n-28)
Different number of ways of arriving at n.
Look at it as a tree that branches out

ps: dunno if this forum should be an easy out for solving homework problems /images/graemlins/smile.gif

let me just add that its possible I'm wrong /images/graemlins/laugh.gif