# How to find recurrence relation for this problem?

How to find a recurrence relation for F(n) the number of ways to make n cents change using only pennies, nickels(5cents), and dimes(10cents)... So for 9 cents, there are 6 ways, which are

1 1 1 1 1 1 1 1 1 ( 9 pennies)
5 1 1 1 1 (1 nickel followed by 4 pennies)
1 5 1 1 1
1 1 5 1 1
1 1 1 5 1
1 1 1 1 5

My attempt so far:

I tried cases up to n=9 just to see how the numbers change

n=0: 1 way (0,0,0) where each element in this vector represent
number of penny, nickel and dime respectively
n=1  1 * (1,0,0)  1 way
n=2  1 * (2,0,0)  1 way
n=3  1 * (3,0,0)  1 way
n=4  1 * (4,0,0)  1 way
n=5  1 * (5,0,0)
1 * (0,1,0)  2 ways
n=6  1 * (6,0,0)
2 * (1,1,0)  3 ways
n=7  1 * (7,0,0)
3 * (2,1,0)  4 ways
n=8  1 * (8,0,0)
4 * (3,1,0)  5 ways
n=9  1 * (9,0,0)
5 * (4,1,0)  6 ways

But I still can't seem to find any sort of subroutine which I can use to build my recurrence.

• Try to find the generating function first. – Mhenni Benghorbal Dec 1 '12 at 22:43
• try breaking up the problem by supposing that you are using $k$ 5's. Then figure out how many such $k$ are possible, which is something akin to $[n/5]$ (floor function). You can account for multiplicities in each configuration by figuring out how many elements you have: $N=(n-5k)+k$, and looking at $N$ choose $k$. Perhaps you can find a simpler recursion by considering how the number of ways goes up from $n$ to $n+1$... – Alex R. Dec 1 '12 at 22:43
• @MhenniBenghorbal: since it’s clear from the OP’s example that different orderings are counted as distinct, generating functions are surely overkill here — this problem could well come up in a course that doesn’t even mention generating functions. – Peter LeFanu Lumsdaine Dec 1 '12 at 23:24
• @PeterLeFanuLumsdaine: It is a suggestion! – Mhenni Benghorbal Dec 1 '12 at 23:32
• I appended some of my attempt so far.. – xiamx Dec 1 '12 at 23:32

If I’m specifying a way to make change for n cents, I have three options: start with a dime, and then make change for the remaining $(n-10)$ cents; or start with a nickel, then make change for the remaining $(n-5)$ cents; or start with a penny, then do the remaining $(n-1)$ cents.
• $F(n-10)$ ways starting with a dime;
• $F(n-5)$ ways starting with a nickel;
• $F(n-1)$ ways starting with a penny.
Adding these up gives: $$F(n) = F(n-1) + F(n-5) + F(n-10)$$