I have the following problem where a shopkeeper makes change for $n$ cents by placing one coin at a time on the counter, keeping a running total; pennies, nickels, and dimes are available. Let $C_n$ be the number of ways to make change for $n$ cents. For example, $C_6$ is 3, since there are 3 possible lists: 111111, 51, and 15. Write a recurrence for $C_n$.
I am having difficulty formalizing the pattern that emerges from $C_1$, $C_2$,..., $C_n$. It seems that there is one, but I'm not sure how to describe it. Can anyone offer a suggestion?
Think about the last coin put down. It can be a penny, or a nickel, or ... So to make $n$ cents you could add a penny to $n-1$ cents or a nickel to $n-5$ cents, or ....