Money change problem using binomial coefficients I am asked to find the change of 260 cents in a country where the system uses pennies, a 2-penny coin and an 8-penny coin.
I can find this using a generating function: $A(x) = \dfrac{1}{(1-x) (1-x^2)(1-x^8)}$ I then look for the coefficient of $x^{260}$ which I can find by computer. But I am asked to use formulae involving binomial coefficients and this confuses me. Any help please? Thank you all
 A: We calculate $[x^{260}]$ the coefficient of $x^{260}$ of $A(x)=\frac{1}{(1-x)(1-x^2)(1-x^8)}$ by consecutively applying the geometric series expansion.

We obtain
  \begin{align*}
\color{blue}{[x^{260}]A(x)}&=[x^{260}]\frac{1}{(1-x)(1-x^2)(1-x^8)}\\
&=[x^{260}]\sum_{j=0}^\infty x^8\cdot\frac{1}{(1-x)(1-x^2)}\tag{1}\\
&=\sum_{j=0}^{\left\lfloor\frac{260}{8}\right\rfloor}[x^{260-8j}]\sum_{k=0}^\infty x^{2k}\cdot\frac{1}{1-x}\tag{2}\\
&=\sum_{j=0}^{32}\sum_{k=0}^{130-4j} [x^{260-8j-2k}]\sum_{l=0}^\infty x^l\tag{3}\\
&=\sum_{j=0}^{32}\sum_{k=0}^{130-4j} 1\tag{4}\\
&=\sum_{j=0}^{32}(131-4j)\\
&=131\cdot 33-4\cdot\frac{32\cdot33}{2}\\
&\,\,\color{blue}{=2211}
\end{align*}

Comment:


*

*In (1) we expand $\frac{1}{1-x^8}$.

*In (2) we restrict the upper bound of the series since other terms do not contribute to $[x^{260}]$ and we use the rule $[x^{p-q}]C(x)=[x^p]x^qC(x)$. We also expand $\frac{1}{1-x^2}$.

*In (3) we select the coefficient of $[x^{260-8j}]$ and restrict the upper limit of the of the series accordingly.

*In (4) we select the coefficient of the geometric series which is always $1$.
