# 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?

## 1 Answer

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)$.
The text passage contains a mathematical problem that involves proving a specific form of a function and a discussion on how to approach the problem. The passage also includes an answer that provides a method to solve the problem by breaking it down into simpler functions.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# 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?

## 1 Answer

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)$.
user
The text passage contains a mathematical problem that involves proving a specific form of a function and a discussion on how to approach the problem. The passage also includes an answer that provides a method to solve the problem by breaking it down into simpler functions.

TYPE: SINGLE_QUESTION_WITH_ANSWER