0

Consider the inequality $x1+x2+x3+x4 ≤n$ where $x1, x2, x3, x4, n ≥ 0$ are all integers. Suppose also that $x2 ≥ 2$, $x3$ is a multiple of 4, and $1 ≤ x4 ≤ 3$. Let cn be the number of solutions of the inequality subject to these restrictions. Find the generating function for the sequence {$Cn : n ≥ 0$} and use it to find a closed formula for $Cn$.

So far I have $x2 = (x^2 + x^3 + x^4 + x^5 ... )$

$x3 = (1 + x^4 + x^8 + x^12 + ...)$

$x4 = (x + x^2 + x^3)$

$x^2/( 1- x) + 1/($1 - x^4) + (1/(1 - x) - 1 - x^4/(1-x))

I don't know how to get the coefficient.

  • 1
    A typesetting note, use _ to use subscripts, and if the subscript or superscript is more than one character long, enclose them in { } braces. x_3 = (1+x^4+x^8+x^{12}+\dots) produces $x_3 = (1+x^4+x^8+x^{12}+\dots)$. Another thing is that you should only use equals signs for equalities. If you wish to say that $x_3$ being what it is implies that you should use $(1+x^4+x^8+\dots)$, then use an arrow, or a squiggle, or something else. – JMoravitz Mar 14 '16 at 00:13
  • 1
    Finally, you should multiply the pieces to the generating function together, not add them. Ideally some nice simplifications should happen. To account for the fact that you wish for them to be adding up to at most $n$, perhaps use an additional "overflow" variable with no restrictions such that it all adds up to $n$ exactly. – JMoravitz Mar 14 '16 at 00:14

1 Answers1

4

Presumably $x_1,x_2,\dots$ are all non-negative integers, else there are clearly infinitely many solutions.

$x_1$ has no restriction beyond being a non-negative integer, so we will use $(1+x+x^2+x^3+\dots)=\frac{1}{1-x}$ in the generating function.

$x_2$ being restricted to integers greater than or equal to two implies we will use a $(x^2+x^3+x^4+\dots)=\frac{x^2}{1-x}$ term in the generating function.

$x_3$ being restricted to non-negative multiples of four implies we will use $(1+x^4+x^8+x^{12}+\dots)=\frac{1}{1-x^4}$ in the generating function.

$x_4$ being restricted to the values of $1,2$ or $3$ implies we will use $(x+x^2+x^3)$ in the generating function.

That we wished for them to add up to at most $n$, let us instead use an overflow variable $x_5=n-x_1-x_2-x_3-x_4$ so that $x_1+x_2+\dots+x_5=n$ exactly, subject to the conditions that $x_5$ is again a non-negative integer. We use another term of $(1+x+x^2+\dots)=\frac{1}{1-x}$ as a result.

Putting all of this together by multiplying the respective pieces, the generating function for the number of solutions will be:

$\sum\limits_{n=0}^\infty c_n x^n = C(x) = \frac{1}{1-x}\cdot \frac{x^2}{1-x}\cdot \frac{1}{1-x^4}\cdot (x+x^2+x^3)\cdot \frac{1}{1-x}=\frac{x^3+x^4+x^5}{(1-x)^3(1-x^4)}$

where the coefficient of $x^n$ is going to be the value of $c_n$. wolfram

I do not personally see this simplifying much more nicely, but here are the first terms of the sequence $0,0,1,4,10,19,32,50,74,104,141,\dots$

As @achillehui points out in the comments below, with the help of software, one can take this further and find it decomposes as $\frac{3}{4(1-x)^4}-\frac{15}{8(1-x)^3} + \frac{19}{16(1-x)^2}+\frac{3}{32(1-x)} - \frac{1}{32(1+x)}-\frac{1-x}{8(1+x^2)}$, yielding the simplification:

$$\begin{align} c_n &= \frac34\binom{n+3}{3} - \frac{15}{8}\binom{n+2}{2} + \frac{19}{16}(n+1) + \frac{3}{32} - \frac{1}{32}(-1)^n -\frac18\Re[(1-i)(-i)^n]\\ &= \left\lfloor\frac{(n^2-2)(2n-3)}{16}\right\rfloor \end{align}$$

JMoravitz
  • 79,518
  • 3
    +1. BTW, with help of a CAS, one can decompose $C(x)$ as $$\frac{3}{4(1-x)^4}-\frac{15}{8(1-x)^3} + \frac{19}{16(1-x)^2}+\frac{3}{32(1-x)} - \frac{1}{32(1+x)}-\frac{1-x}{8(1+x^2)}$$ From this, one can deduce $$\begin{align} c_n &= \frac34\binom{n+3}{3} - \frac{15}{8}\binom{n+2}{2} + \frac{19}{16}(n+1) + \frac{3}{32} - \frac{1}{32}(-1)^n -\frac18\Re[(1-i)(-i)^n]\ &= \left\lfloor\frac{(n^2-2)(2n-3)}{16}\right\rfloor \end{align} $$ – achille hui Mar 14 '16 at 01:20