Given $M\geq 1$ coins of denominations $a_1, \ldots, a_M$, I want to determine the number of ways to make change to obtain a value of $n\geq 0$ coins. We will assume that we have an unrestricted number of coins of each denomination.
For example, if I have only pennies and nickels, the number of ways to obtain $10$ cents is 3 (two nickels, a nickel and five pennies, or 10 pennies).
Now say I only have one kind of coin and its denomination is $a_1$. Then with my unlimited number of coins I can only form change that consists of multiples of $a_1$. I can easily create a generating function whose coefficients tell us the number of ways to make change for $a_1k$ coins for all $k \geq 0$, namely $$\sum_{k=0}^\infty (x^{a_1})^k=\frac{1}{1-x^{a_1}}.$$ All the coefficients are $1$ because there is only one way to make change for $a_1k$ if I only have coins of denomination $a_1$.
Now what I am trying to determine is the generating function whose coefficients give me the number of ways to make change for $n$ when I have more than one denomination. I believe that the answer is $$\prod_{i=1}^M\left(\sum_{k=0}^\infty (x^{a_i})^k \right)=\prod_{i=1}^M \frac{1}{1-x^{a_i}}, $$ but I do not know how to prove this. Could someone provide some insight or reference a good proof? Thank you!
There's a quick intermediate step that may help you out. Let $c_n$ be the number of ways to make change with $a_1,\ldots,a_M$ for $n$. Then we have $$\sum_{n \geq 0} c_n x^n = \sum_{k_1,k_2,\ldots, k_M} x^{k_1 a_1 + \cdots + k_M a_m} = \prod_{i=1}^M \left( \sum_{k_i = 0}^\infty x^{k_i a_i}\right) = \prod_{i = 1}^M \frac{1}{1 - x^{a_i}}\,.$$