# find a recurrence relation

• Jun 4th 2008, 08:59 AM
robocop_911
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?
• Jun 13th 2008, 06:13 AM
PaulRS
Okay, let's call $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 $a_n$ ways, now if we want to add a coin of 2 dollars this can be done in $a_{n-1}$ ways (since we need n-1 dollars), and so on...

Summing all the possibilities:

$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 $a_n=0$ if $n<0$ and $a_{0}=1$ (there's only one way of paying nothing) and then $a_{n+1}$ is defined by (1) if $n\geq{0}$
• Jun 13th 2008, 09:17 AM
natarajchakraborty
Quote:

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

Summing all the possibilities:

$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?
Quote:

now if we want to add a coin of 2 dollars this can be done in $a_{n-1}$ ways (since we need n-1 dollars), and so on...
well I got it about $2a_{n-4}$ since there are two ways to pay a $5$ dollar, by coin and a bill....

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

but still I need some explanation.... am I right in my thinking....
cheers...
• Jun 13th 2008, 09:32 AM
PaulRS
Quote:

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

I think it is about assumption that to pay a bill of $n$ we need $a_{n}$ so we need $a_{n-1}$ ways to pay a bill of $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 $a_n$ ways, thus if the thing you want to hand in last is a 1 dollar coin you can do this in $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