# 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 \$\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}\$
• 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 \$\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?
Quote:

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...
• 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 \$\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