# Generating function and its closed form

Consider the inequality $x_1 + x_2 + x_3 + x_4 ≤n$ where $x_1,x_2,x_3,x_4,n ≥ 0$ are all integers. Suppose also that $x_2 ≥ 2$, that $x_3$ is a multiple of 4, and $1 ≤ x_4 ≤ 3$. Let $c_n$ be the number of solutions of the inequality subject to these restrictions. Find the generating function for the sequence $\{c_n: n≥0\}$ and use it to ﬁnd a closed formula for $c_n$.

I have figured out that $$G(x)= \frac{1}{1-x^4}\frac{1}{1-x}(x^2+x^3+x^4)(x+x^2+x^3)$$ because I analyzed the conditions for each variable separately. I am unsure how to solve the closed form, what steps to take because this is a weird equation where I can't seem to simplify stuff.

Please let me know if you have any questions.

• If we check the valuation of your $G$, it is $-1$. I think that its valuation should be $3$ because $c_0,c_1,c_2$ have to be $0$ (because of the conditions on $x_2$ and $x_4$) and $c_3\geq 1$ because $0+2+0+1=3$ is a solution. Maybe you could explain how you got $G$? – Clément Guérin Apr 9 '15 at 16:49
• Idk but it was edited wrong because the (1+x+x^2) and (x+x^2+x^3) had been on the top – Alex Apr 10 '15 at 15:18
• I noticed that I had misread the question (regarding the second variable, x2) so that was the part I had messed up. But everything else was right – Alex Apr 10 '15 at 15:19

$x_1$ can be any non-negative integer: $$1+x+x^2+x^3+x^4+\ldots$$ $x_2$ is any integer greater than or equal to $2$: $$x^2+x^3+x^4+x^5+\ldots$$ $x_3$ is a non-negative multiple of four: $$1+x^4+x^8+x^{12}+\ldots$$ $x_4$ is in $\{1,2,3\}$: $$x+x^2+x^3$$
Multiplied together: $$\frac1{1-x}\cdot\frac{x^2}{1-x}\cdot\frac1{1-x^4}\cdot(x+x^2+x^3)$$ $$=\frac{x^3+x^4+x^5}{(1-x)^2(1-x^4)}$$