0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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 ....

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.