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 find 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.

  • $\begingroup$ 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$? $\endgroup$ – Clément Guérin Apr 9 '15 at 16:49
  • $\begingroup$ Idk but it was edited wrong because the (1+x+x^2) and (x+x^2+x^3) had been on the top $\endgroup$ – Alex Apr 10 '15 at 15:18
  • $\begingroup$ 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 $\endgroup$ – Alex Apr 10 '15 at 15:19

First, let's sort out what the generating function is.

$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)}$$


I would do: $$\newcommand{\u}[2]{\underbrace{#1}_{#2}} \u{(x^0+x^1+x^2+...)}{x_1}\u{(x^2+x^3+x^4+...)}{x_2}\u{(x^0+x^4+x^8+...)}{x_3}\u{(x^1+x^2+x^3)}{x_4}$$ Or: $$\newcommand{\c}[2]{{}^{#1}{\mathbb C}_{#2}}\frac{1}{1-x}\frac{x^2}{1-x}\frac{1}{1-x^4}\frac{x(1-x^3)}{1-x}=x^3(1-x^3)(1-x)^{-4}(1+x)^{-1}(1+x^2)^{-1}\\=x^3(1-x^3)\sum_{r=0}^{\infty}\c{r+3}rx^r\sum_{s=0}^{\infty} (-x)^s\sum_{t=0}^{\infty}(-x^2)^t$$

  • $\begingroup$ care to explain why -1? $\endgroup$ – RE60K Apr 10 '15 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.