Solution

Find a recurrence formula for the number of ways to put $n$ cents in a machine if we use identical nickles, dimes, and quarters. (You may assume $5 \mid n$.)


Suppose we denote the number of ways to put $n$ cents in a machine if we use identical nickles, dimes, and quarters by $f(n)$.

The trick here is to "think recursively" and tell yourself that you already know that when $k \lt n$, you can put $k$ cents in the machine in $f(k)$ ways.

As you start dropping change in the machine, you might start by putting in either a nickel, a dime, or a quarter. Let us suppose you put in a nickel. Now you have to ask yourself how many ways can you put in the remaining $n-5$ cents. But $n-5 \lt n$, so this can be done in $f(n-5)$ ways.

If instead, you had put in a dime first, then you have to ask yourself how many ways can you put in the remaining $n-10$ cents. Here again, $n-10 \lt n$, so this can be done in $f(n-10)$ ways.

Lastly, if you first dropped a quarter in the machine, you similarly have $f(n-25)$ ways to put in the remaining change.

Taking these cases together, we arrive at our recursive relationship:

$$f(n) = f(n-5) + f(n-10) + f(n-25)$$

All that remains is to identify what happens in the first cases. Note that $f(0) = 1$ and $f(5) = 1$ by inspection. Further, $f(n) = 0$ if $n \lt 0$, as we would need "negative coins" otherwise.

This completes our recursive definition for $f(n)$.