Formula for the number of integer solutions of an equation (using generating functions)

438 Views Asked by At

Let $a_n$ be the number of integer solutions of $$i+3j+3k=n$$ where $i \geq 0, j \geq 2, k \geq 3$.

I want to use the generating function of $(a_n)_{n \in \mathbb N}$ to get a formula for $a_n$.

We just introduced generating functions, so I'm fairly new to this stuff and hope you can help me solve this problem.

I began by interpreting the problem as a power series. Without the restrictions for $i, j, k$ I get $$(1+x+x^2+x^3+\dots)(1+x^3+x^6+x^9+\dots)^2.$$ Accounting for $i \geq 0, j \geq 2, k \geq 3$ should get me something like $$(1+x+x^2+x^3+\dots)(x^6+x^9+x^{12}+\dots)(x^9++x^{12}+x^{15}+\dots).$$ Is that correct?

Now I tried to simplify this like this: $$1+x+x^2+x^3+\dots = \frac{1}{1-x}$$ $$x^6+x^9+x^{12}+\dots =(1+x^3+x^6+x^9+x^{12}+\dots)-(1+x^3) =\frac{1}{1-x^3}-(1+x^3) =\frac{x^6}{1-x^3}$$ and likewise $$x^9++x^{12}+x^{15}+\dots = \frac{x^9}{1-x^3}.$$ So I have $$(1+x+x^2+x^3+\dots)(x^6+x^9+x^{12}+\dots)(x^9++x^{12}+x^{15}+\dots) =\frac{x^{15}}{(1-x)(1-x^3)^2}.$$

I hope I didn't make a mistake already. In any case, here I'm stuck. I have to find a formula for the $n$-th coefficient in this power series, but I don't know how to do it.


[edit]

I'm still quite confused, but I'll try to go over it again one by one. Here is again the complete (and hopefully correct) partial fraction decomposition and my try to expand it: $$\frac{1}{(1 - x)^3 (x^2 + x + 1)^2} \\ =\frac{1}{27} \frac{7x + 8}{x^2 + x + 1} + \frac{1}{9} \frac{2x+1}{(x^2 + x + 1)^2} + \frac{1}{27} \frac{7}{1-x} - \frac{1}{9} \frac{2}{(1-x)^2} + \frac{1}{9} \frac{1}{(1-x)^3} \\ =\frac{1}{27} \frac{(7x + 8)(1-x)}{(1-x^3)} + \frac{1}{9} \frac{(2x+1)(1-x)^2}{(1-x^3)^2} + \frac{1}{27} \frac{7}{1-x} - \frac{1}{9} \frac{2}{(1-x)^2} + \frac{1}{9} \frac{-1}{(1-x)^3} \\ =\frac{ (7x + 8)(1-x)}{27} \sum x^{3n} + \frac{ (2x+1)(1-x)^2}{9} \sum (n+1) x^{3n} + \frac{7}{27} \sum x^n - \frac{2}{9} \sum (n+1) x^n + \frac{1}{9} \sum x^{3n}.$$

Still to do: Multiply by $x^{15}$ and find the coefficient of $x^k$.

2

There are 2 best solutions below

5
On BEST ANSWER

Since you seem to have run out of steam, I'll finish off what you've started. First note that you have a sign error in the second to last term: it should be $+ \frac{2}{9} \sum (n+1) x^n$. Thus the series expansion for the generating function is \begin{align*} \frac{-7x^2 - x + 8}{27} \sum_{n \geq 0} x^{3n} &+ \frac{2x^3 - 3x^2 + 1}{9} \sum_{n \geq 0} (n+1) x^{3n}\\ &+ \frac{7}{27} \sum_{n \geq 0} x^n + \frac{2}{9} \sum_{n \geq 0} (n+1) x^n + \frac{1}{18} \sum_{n \geq 0} (n^2 + 3n + 2) x^n \, . \end{align*}

The coefficient of $x^m$ in these series depends on whether $m \equiv 0, 1$ or $2$ mod ${3}$. If $m \equiv 0 \pmod{3}$, then the coefficient is \begin{align} &\frac{8}{27} + \frac{1}{9}\left(2 \left(\frac{m-3}{3} + 1\right) + \frac{m}{3} + 1 \right) + \frac{7}{27} + \frac{2}{9}(m+1) + \frac{1}{18}(m^2 + 3m + 2)\\ &= \frac{1}{18}m^2 + \frac{1}{2}m + 1 \, . \end{align} (Note that the second sum contributes two terms since $3n+3 \equiv 0 \pmod{3}$ as well.) The last $3$ terms in the first line of the above formula remain the same whether $m \equiv 0, 1$ or $2$ mod ${3}$.

[Edit: A bit more on how I got this. Let's consider the coefficient of $x^m$ in the first sum $\frac{-7x^2 - x + 8}{27} \sum_{n \geq 0} x^{3n}$. Distributing, this sum is equal to $$ \frac{-7}{27}\sum_{n \geq 0} x^{3n+2} + \frac{-1}{27} \sum_{n \geq 0} x^{3n+1} + \frac{8}{27} \sum_{n \geq 0} x^{3n} \, . $$ If $m \equiv 0 \pmod{3}$, then the first to sums do not contribute to the coefficient of $x^m$. Why? Because all their powers of $x$ are congruent to $2$ and $1$, respectively. Only the last sum contributes $\frac{8}{27}$ to the coefficient of $x^m$ when $n = m/3$. Similarly, only the second sum contributes when $m \equiv 1 \pmod{3}$, and the first when $m \equiv 2 \pmod{3}$. The same considerations work for finding the coefficient of $x^m$ in $\frac{2x^3 - 3x^2 + 1}{9} \sum_{n \geq 0} (n+1) x^{3n}$.]

Similar calculations for $m \equiv 1, 2 \pmod{3}$ imply that the coefficient of $x^m$ is $$ \begin{cases} \frac{1}{18}m^2 + \frac{1}{2}m + 1 & \text{if } m \equiv 0 \pmod{3}\\ \frac{1}{18}m^2 + \frac{7}{18}m + \frac{5}{9} & \text{if } m \equiv 1 \pmod{3}\\ \frac{1}{18}m^2 + \frac{5}{18}m + \frac{2}{9} & \text{if } m \equiv 2 \pmod{3} \end{cases} \, . $$

As vonbrand points out in his answer, we could've instead factored the quadratic $1 + x + x^2$ into linear factors with third roots of unity, which would have lead to the same periodic behavior with period $3$.

Finally, as you pointed out, we still haven't taken care of that $x^{15}$. It's very simple, though: to obtain the coefficient of $x^m$ in $\frac{x^{15}}{(1 - x)^3 (x^2 + x + 1)^2}$, we simply take the coefficient of $x^{m-15}$ in $\frac{1}{(1 - x)^3 (x^2 + x + 1)^2}$. For instance, to compute the coefficient of $x^{22}$, we substitute $m = 22 - 15 = 7$ into the formula for $m \equiv 1 \pmod{3}$, which yields $6$.

It turns out that these formulas can be simplified dramatically. Using the formulas above (or Wolfram Alpha), we find that the Maclaurin series for the generating function is $$ x^{15}+x^{16}+x^{17}+3 x^{18}+3 x^{19}+3 x^{20}+6 x^{21}+6 x^{22}+6 x^{23}+10 x^{24}+10 x^{25}+10 x^{26}+15 x^{27}+15 x^{28}+15 x^{29}+ \cdots \, . $$ These coefficients are the triangular numbers $T_n = \binom{n+2}{2} = \frac{(n+2)(n+1)}{2}$ repeated $3$ times each. This can also be seen from the formulas above: letting \begin{align*} f(m) &= \frac{1}{18}m^2 + \frac{1}{2}m + 1\\ g(m) &= \frac{1}{18}m^2 + \frac{7}{18}m + \frac{5}{9}\\ h(m) &= \frac{1}{18}m^2 + \frac{5}{18}m + \frac{2}{9} \end{align*} then $$ f(3n) = g(3n+1) = h(3n+2) = \frac{1}{2} n^2 + \frac{3}{2}n + 1 = \binom{n+2}{2} \, . $$ Thus a simpler formula for the coefficient of $x^n$ is $$ \frac{1}{2} \left(\left\lfloor \frac{n-15}{3} \right\rfloor + 2\right) \left(\left\lfloor \frac{n-15}{3} \right\rfloor + 1\right) \, . $$

3
On

OK, use generating functions. Note that $1 - z^3 = (1 - \omega z) (1 - \omega^2 z) (1 - z)$, where $\omega = -\frac{1}{2} + \mathrm{i} \frac{\sqrt{3}}{2}$ and $\omega^3 = 1$: \begin{align} [z^n] z^{15} (1 + z &+ z^2 + \ldots) (1 + z^3 + z^6 + \ldots)^2 \\ &= [z^{n - 15}] \frac{1}{(1 - z) (1 - z^3)^2} \\ &= [z^{n - 15}] \frac{1}{(1 - z)^3 (1 - \omega z)^2 (1 - \omega^2 z)^2} \end{align} This can be split into partial fractions, but the coefficients are very ugly. They can be simplified by $\omega^2 + \omega + 1 = 0$ and $\omega^3 = 1$. Use of a computer algebra system is mandatory.

Once you've got the partial fractions, you can use: $$ \binom{-m}{k} = (-1)^k \binom{k + m - 1}{m - 1} $$ The imaginary components cancel out, and you get real coefficients. One way to express them is to use Euler's formula: $$ \omega^n = \exp( \mathrm{i} \frac{2 \pi n}{3} ) = \cos \frac{2 \pi n}{3} + \mathrm{i} \sin \frac{2 \pi n}{3} $$