# On the number of ways to make $50n$ cents out of pennies, nickels, dimes and quarters

Let $f(n)$ be the number of ways to make n cents out of pennies, nickels, dimes and quarters (1c, 5c, 10c, 25c).

Prove that $f(50n) = an^3 + bn^2 + cn + 1$ for some constants $a, b, c.$

I have found the generating function of $f$ is

$$f(x)=\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{25})}.$$

I can produce a generating function $g(x)$ whose terms are just the terms of $f$ whose powers are multiples of 50 using the formula

$$g(x) = \frac{1}{50}\sum\limits_{k=1}^{50}{f(x e^{2\pi i k/50})},$$

but in practice it seems hard to simplify this expression for $g$ and extract a recurrence for $f(50n)$ from it.

Is there a better way to approach this problem?

Let $A(n)$ be the number of ways of making $5n$ cents from pennies and nickels.
Let $B_1(n)$ be the number of ways of making $10n$ cents from pennies, nickels and dimes.
Let $B_2(n)$ be the number of ways of making $10n+5$ cents from pennies, nickels and dimes.
Let $C_1(n)$ be the number of ways of making $50n$ cents from pennies, nickels, dimes and quarters.
Let $C_2(n)$ be the number of ways of making $50n+25$ cents from pennies, nickels, dimes and quarters.
$A(n)$ is simple. It is linear.
You can calculate $B_1(n)$ and $B_2(n)$ as a sum of $A(m)$ by adding over the number of dimes. They are quadratic.
The formulas for $C_1(n)$ and $C_2(n)$ will be sums of $B_1(m)$ and $B_2(m)$.