Money Dealing Strategies - Find Recurrence Relation

[Goldenwind]

Homework Statement

A country uses as currency coins with values of 1 peso, 2 pesos, 5 pesos, and 10 pesos and bills with values of 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find a recurrence relation for the number of ways to pay a bill of n pesos if the order in which the coins and bills are paid matters.

Reminder: I'm just asking for a hint, DO NOT solve this.

Homework Equations

To see an example of a recurrence relation, see my other thread.

The Attempt at a Solution

If I were approaching this in real life, I'd think of it like vending change after a customer bought something.

Say their change is 588 pesos.
I'd give them five 100 pesos bills, still owing 88 pesos.
Then give one 50 pesos bill, still owing 38 pesos.
Then give one 20 pesos bill, still owing 18 pesos.
Then give one 10 pesos bill/coin, still owing 8 pesos.
Then give one 5 pesos bill/coin, still owing 3 pesos.
Then give one 2 pesos coin, still owing 1 pesos.
Then give one 1 pesos coin.

But this is just one way. There are many, many, many other ways to do this, such as 588x1Pesos, 294x2Pesos, (5x100Pesos + 44x2Pesos), and so on.

I could program this in Java, using a method and multiple "Is a > b?" conditions, but clueless as to how to do this in a recursive formula $a_n$.

Another reminder: Hint only, don't solve.

 

[Secui]

Hi Goldenwind

Funny coincidence, but I've been dealing with the exact same problem and in fact I think I am in the same class as you because I have seen your posts before. I did manage to find a solution earlier on, and the resource I looked at that helped me is in the following link:

http://books.google.ca/books?id=vIf...OEjAG6n_jdBg&sig=wWKIPPcJCJaNT4r4nAXEPVXeHK8"

That text deals with a similar problem and I found it helpful. Also note that in the answers section of the textbook it shows that for when n = 17, the result will be 9494, so if you feel like writing out all the terms (or if you're like me, you'd write a computer program to do it for you) you have a rough means of checking your answer.

I hope I didn't just scare you to death. Good luck with the problem.