text: # 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)$.