Money change problem using binomial coefficients

Question

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

Answer 1

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