Using generating functions, find the number of ways to make change for a ${$100}$ bill using only dollar coins and ${$1, $5, \text{and}~$10}$ bills.
My answer: I had $\frac{1}{(1-x)^2}\cdot(1-x^5)\cdot(1-x^{10})=\frac{1}{(1-x)^2}\cdot(1-x^5)^2\cdot(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?
On
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$$
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.