Generating functions of bills Using generating functions, ﬁnd the number of ways to make change for a $\$$100 
bill using only dollar coins and $\$$1, $\$$5, and $\$$10 bills.
My answer: I had $1/(1-x)^2*(1-x^5)*(1-x^{10})=1/(1-x)^2*(1-x^5)^2*(1+x^5)$.
I know I need to find the coefficient of $x^{100}$. What should I do next? My guess is partial fractions but the computation looks very long. So is there an easier way to determine the coefficient?
 A: Rewrite the generating function $G(x)$ as
\begin{align*}
G(x) &= \frac{1}{\left(1-x\right)^2\left(1-x^5\right)\left(1-x^{10}\right)}\\
     &= \frac{\left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3}{\left(1-x^{10}\right)^4}\\
     &= \left(1+x+x^2+x^3+x^4\right)^2\left(1+x^5\right)^3\sum_k \binom{k+3}{3} x^{10\, k}
\end{align*}
Now, extracting $x^{10k}$ gives
$$[x^{10k}]G(x) = \binom{k+3}{3} + 15 \binom{k+2}{3}+4 \binom{k+1}{3}$$
For $k=10$, we get
$$[x^{100}]G(x) = \binom{13}{3} + 15 \binom{12}{3}+4 \binom{11}{3} = 4246$$
A: So the generating function expansion can be truncated to:
$ (1+x+x^2+\cdots +x^{100})^2. (1+x^5+x^{10}+\cdots +x^{100}). (1+x^{10}+x^{20}+\cdots + x^{100})$
You're then looking for the coefficient of $x^{100}$.
The first two terms (for the 1 dollar coins and the 1 dollar bills) become 
$1+2x+3x^2+\cdots +101x^{100}$ plus higher powers. Only the powers that are multiples of 5 are now relevant. So you need only consider:
$1+6x^5+11x^{10}+\cdots+101x^{100}$.
This can be multiplied by the next term, and in a similar way, discard all powers that are odd multiples of 5:
$1+18x^{10}+(1+6+11+16+21)x^{20}+...$
Repeat for the final multiplication. 
