3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

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