Number of non-negative integer solutions of an equation using generating functions

Question

Using convolution, find how many non-negative integer solutions of

$$\begin{aligned} x_1 + 5 x_2 &= n\\ x_1 + 5 x_2 &= 60\end{aligned}$$

Is anyone able to solve this problem or figure out the idea? Thank you so much.

Answer 1

Here's a combinatorial interpretation: the number of solutions to the second equation is the number of ways to make 60 cents in change using 1 cent and 5 cent coins.

I assume that the second equation is a special case of the first, and that you want to know how to solve both. The method for $n=60$ illustrates the general case.

For a non-negative integer $a$, let $r_a$ be the number of non-negative integer solutions to $x_1=a$ and let $s_a$ be the number of non-negative integer solutions to $5x_2=a$. So $r_a$ is the number of ways to make $a$ cents in change using 1 cent coins alone, and $s_a$ is the number of ways of making $a$ cents in change using 5 cent coins alone. Can you characterize $r_a$ and $s_a$? The number of non-negative integer solutions to $x_1+5x_2=60$ is then given by the convolution $$r_0s_{60}+r_1s_{59}+\ldots+r_{60}s_0.$$ This is the coefficient of $x^{60}$ in the product of the generating functions for the coefficients $r_a$ and $s_a,$ $$(r_0+r_1x+r_2x^2+\ldots)(s_0+s_1x+s_2x^2+\ldots).$$

You should have found that $r_a=1$ for all $a$ and that $s_a=1$ for $a$ divisible by 5 and $s_a=0$ otherwise. Then $$r_0+r_1x+r_2x^2+\ldots=1+x+x^2+\ldots=\frac{1}{1-x}$$ and $$s_0+s_1x+s_2x^2+\ldots=1+x^5+x^{10}+\ldots=\frac{1}{1-x^5}.$$ Here's one method for extracting the coefficient of $x^n$ in the generating function $$\frac{1}{(1-x)(1-x^5)}.$$ Write $$\frac{1}{1-x}=\frac{1+x+x^2+x^3+x^4}{1-x^5}.$$ Then $$\frac{1}{(1-x)(1-x^5)}=\frac{1+x+x^2+x^3+x^4}{(1-x^5)^2}=(1+x+x^2+x^3+x^4)\sum_{r=0}^\infty\binom{-2}{r}(-x^5)^r,$$ where $\binom{-2}{r}=\frac{(-2)(-3)\ldots(-2-r+1)}{r!}$ is the generalized binomial coefficient. You can show that $(-1)^r\binom{-2}{r}=r+1$, and so the generating function is $$(1+x+x^2+x^3+x^4)\sum_{r=0}^\infty(r+1)x^{5r}.$$ The $x^{60}$ term comes from multiplying the $1=x^0$ term in the polynomial with the $r=12$ term in the summation. Hence the answer is $1\cdot(12+1)=13$.

This method can be generalized to the case where you have additional coin values, say 10 cent coins.

Answer 2

Since the left hand sides coincide, we immediately get $n = 60$, and the system reduces to the single equation $$x_1 + 5x_2 = 60$$ or equivalently $$x_1 = 60 - 5x_2 = 5(12 - x_2).$$ Now $x_1$ is non-negative iff $x_2\leq 12$. So there are exactly the $13$ non-negative solutions $$(x_1,x_2)\in\{(60 - 5x_2, x_2) \mid x_2\in\{0,\ldots,12\}\}.$$