# How to find the generating function

What is the generating function for ${a_k}$, where $a_k$ is the number of solutions of $x_1 + x_2 + x_3 = k$ when $x_1,x_2,x_3$ are integers with $x_1 \geq 2$, $0 \leq x_2 \leq 3$, and $2 \leq x_3 \leq 5$?

I know that the answer of this problem is $x^4(1+x+x^2+x^3)^2/(1-x)$. I want to know how to find the generating function in detail. Please help me!

Let me change the names of the variables in hopes of reducing confusion later: instead of $x_1,x_2$, and $x_3$, I’ll use $y_1,y_2$, and $y_3$. Eventually my generating function will use the indeterminate $x$, but temporarily I’m going to split it into three indeterminates $x_1,x_2$, and $x_3$: for $k=1,2,3$ the exponent on $x_k$ will keep track of a possible value of $y_k$. The possible values of $y_1$ are the integers greater than or equal to $2$, represented by

$$x_1^2+x_1^3+x_1^4+\ldots=\sum_{n\ge 2}x_1^n\;.$$

The only possible values of $y_2$ are $0,1,2$, and $3$, represented by

$$x_2^0+x_2^1+x_2^2+x_2^3\;.$$

And the only possible values of $y_3$ are $2,3,4$, and $5$, represented by

$$x_3^2+x_3^3+x_3^4+x_3^5\;.$$

Multiply these three expressions together to get

$$(x_1^2+x_1^3+x_1^4+\ldots)(x_2^0+x_2^1+x_2^2+x_2^3)(x_3^2+x_3^3+x_3^4+x_3^5)\;,$$

and imagine actually carrying out the multiplication. Each term of the product will have the form $x_1^kx_2^\ell x_3^m$, where $k\ge 2$, $0\le\ell\le 3$, and $2\le m\le 5$. Now drop the subscripts on $x_1,x_2$, and $x_3$, making them all simply $x$: each term of the product will have the form $x^{k+\ell+m}$ for some integers $k,\ell$, and $m$ such that $k\ge 2$, $0\le\ell\le 3$, and $2\le m\le 5$. Moreover, every possible combination of $k,\ell$, and $m$ satisfying those constraints will occur. Thus, when you collect like terms, you’ll have one copy of $x^n$ for each combination of $k,\ell$, and $m$ such that $k+\ell+m=n$, $k\ge 2$, $0\le\ell\le 3$, and $2\le m\le 5$. That is, the coefficient of $x^n$ will be the number of solutions to $y_1+y_2+y_3=n$ satisfying the given conditions.

This means that the desired generating function is

$$(x^2+x^3+x^4+\ldots)(x^0+x^1+x^2+x^3)(x^2+x^3+x^4+x^5)\;,$$

and we need only simplify it. First, $x^2+x^3+x^4+x^5=x^2(1+x+x^2+x^3)$, so

$$(x^0+x^1+x^2+x^3)(x^2+x^3+x^4+x^5)=x^2(1+x+x^2+x^3)^2\;.$$

Then

$$x^2+x^3+x^4+\ldots=\sum_{n\ge 2}x^n=x^2\sum_{n\ge 0}x^n=\frac{x^2}{1-x}$$

from the formula for a geometric series. Now just put the pieces togeter to get

$$\frac{x^2}{1-x}\cdot x^2(1+x+x^2+x^3)=\frac{x^4(1+x+x^2+x^3)}{1-x}\;.$$