Thread: find a recurrence relation

Find a recurrence relation for the number of ways to pay a bill of n dollars if the order in which the coins and bills are paid matters.
We have "coins" of 1, 2, 5, 10$ and "bills" of 5, 10, 20, 50 and 100$.

How to begin doing this sum?

Okay, let's call the number of ways in which you can the bill of n dollars.

Note that if we want to pay a bill of n+1 dollars we can add a coin of a dollar to n dollars, this can be done in ways, now if we want to add a coin of 2 dollars this can be done in ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

(1)

Now for this to always make sense we define if and (there's only one way of paying nothing) and then is defined by (1) if

Originally Posted by PaulRS

now if we want to add a coin of 2 dollars this can be done in ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

Wow, but I got some doubts.... the derivation is quite tough for me....


How this works?

now if we want to add a coin of 2 dollars this can be done in ways (since we need n-1 dollars), and so on...

well I got it about since there are two ways to pay a dollar, by coin and a bill....

I think it is about assumption that to pay a bill of we need so we need ways to pay a bill of


but still I need some explanation.... am I right in my thinking....
cheers...

Originally Posted by natarajchakraborty

Wow, but I got some doubts.... the derivation is quite tough for me....


How this works?


well I got it about since there are two ways to pay a dollar, by coin and a bill....

I think it is about assumption that to pay a bill of we need so we need ways to pay a bill of



but still I need some explanation.... am I right in my thinking....
cheers...

Forget about the bill, the only thing you want is to know in how many ways you can hand in n+1 dollars using that type of coins and notes.

If we want to GIVE A $1 coin at the end (for we care about the order), we need to have $N otherwise will NOT be giving $N+1, but we can give $N dollars in ways, thus if the thing you want to hand in last is a 1 dollar coin you can do this in ways

Now the other cases (according to what you want to give last) are very similar and so, by the sum rule we have what I'd posted