Ways of Changing 85/90 dollars

Question

The number of ways of changing 85 dollars with 1,5,10 and 20 dollar bills should be the coefficient of $x^{85}$ in $(1+x+x^2+\ldots+x^{85})(1+x^5+\ldots+x^{85})(1+x^{10}+\ldots+x^{80})(1+x^{20}+\ldots+x^{80})$, that is, $\frac{(1-x^{81})^2}{(1-x)(1-x^5)}\cdot\frac{(1-x^{86})^2}{(1-x^{10})(1-x^{20})}$, however if we want to change 90 dollars with 5,10,20 and 50 bills we can just say its the coefficient of $x^{90}$ in $\frac{1}{(1-x^5)(1-x^{10})(1-x^{20})(1-x^{50})}$. Why can we "eliminate" everything in the numerator in that case?

Answer 1

First thing, your formula for finite geometric sums is incorrect. It should be $$1+x^a+x^{2a}+x^{3a}+x^{4a}+\ldots +x^{na}=\frac{x^{(n+1)a}-1}{x-1}$$

So what you actually should have is that in the $85$ case, it is the coefficient of $x^{85}$ in $$\frac{(1-x^{86})(1-x^{90})(1-x^{90})(1-x^{100})}{(1-x)(1-x^5)(1-x^{10})(1-x^{20})}$$

The reason why you can omit all the terms of the numerator (aside from $1$) is from considering the expansion of $(1-x^{86})(1-x^{90})(1-x^{90})(1-x^{100})$. This will of course contain the term $1$. The rest of the terms, however, will be powers of $x$ that are greater than $x^{85}$. When multiplied with the series expansion of the denominator, none of these other terms will affect the coefficient of $x^{85}$ because they are already bigger than $x^{85}$.

Another reason to see this is from a similar reasoning. While you are trying to compute the coefficient of $x^{85}$ in the finite polynomial $$(1+x+x^2+\ldots+x^{85})(1+x^5+\ldots+x^{85})(1+x^{10}+\ldots+x^{80})(1+x^{20}+\ldots+x^{80})$$ What's the difference between the coefficient of $x^{85}$ in the original polynomial and $$(1+x+x^2+\ldots+x^{85}+x^{86})(1+x^5+\ldots+x^{85})(1+x^{10}+\ldots+x^{80})(1+x^{20}+\ldots+x^{80})$$ You will see that there is none, and we can keep on adding powers higher than $x^{85}$ because they do not affect the coefficient of $x^{85}$ in the expansion. Hence, this is the exact same as computing the coefficient of $x^{85}$ in the expansion of $$1+x+x^2+\ldots)(1+x^5+\ldots)(1+x^{10}+\ldots)(1+x^{20}+\ldots)$$ $$=\frac{1}{(1-x)(1-x^5)(1-x^{10})(1-x^{20})}$$