# Thread: find a recurrence relation

1. ## 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?

2. Okay, let's call $\displaystyle a_n$ 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 $\displaystyle a_n$ ways, now if we want to add a coin of 2 dollars this can be done in $\displaystyle a_{n-1}$ ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

$\displaystyle a_{n+1}=a_{n}+a_{n-1}+2a_{n-4}+2a_{n-9}+a_{n-19}+a_{n-49}+a_{n-99}$ (1)

Now for this to always make sense we define $\displaystyle a_n=0$ if $\displaystyle n<0$ and $\displaystyle a_{0}=1$ (there's only one way of paying nothing) and then $\displaystyle a_{n+1}$ is defined by (1) if $\displaystyle n\geq{0}$

3. Originally Posted by PaulRS
now if we want to add a coin of 2 dollars this can be done in $\displaystyle a_{n-1}$ ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

$\displaystyle a_{n+1}=a_{n}+a_{n-1}+2a_{n-4}+2a_{n-9}+a_{n-19}+a_{n-49}+a_{n-99}$
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 $\displaystyle a_{n-1}$ ways (since we need n-1 dollars), and so on...
well I got it about $\displaystyle 2a_{n-4}$ since there are two ways to pay a $\displaystyle 5$ dollar, by coin and a bill....

I think it is about assumption that to pay a bill of $\displaystyle n$ we need $\displaystyle a_{n}$ so we need $\displaystyle a_{n-1}$ ways to pay a bill of $\displaystyle n-1$

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

4. 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 $\displaystyle 2a_{n-4}$ since there are two ways to pay a $\displaystyle 5$ dollar, by coin and a bill....

I think it is about assumption that to pay a bill of $\displaystyle n$ we need $\displaystyle a_{n}$ so we need $\displaystyle a_{n-1}$ ways to pay a bill of $\displaystyle n-1$

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 $\displaystyle a_n$ ways, thus if the thing you want to hand in last is a 1 dollar coin you can do this in $\displaystyle a_n$ 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