Generating functions for the solutions to $3x_1 + x_2 = n$

Question

I need to find the amount of solutions with non negative integers to the equation $x_1 + x_2 + x_3 = n$ with $x_2 = 2x_1$.

I transformed it to $y_1 + y_2 = n$ when $y_1=3x_1, y_2 = x_3$

(because $x_1 + x_2 + x_3 = n$ here is the same as $x_1 + 2x_1 + x_3 = n$, which is $3x_1 + x_3 = n$).

Using generating functions $$[x^n] = \frac {1}{(1-x^3)(1-x)}$$ which is by expanding $1-x^3$:$$[x^n] = \frac {1}{(1-x)^2(1+x+x^2)}$$ The problem here is that that the expansion of $(1+x+x^2)$ involves complex numbers so I'm not sure how to proceed from here.

Answer 1

You can proceed in two ways. First, you can use the formula

$$ \frac{1}{1 - x} \sum_{n} a_n x^n = \sum_n \left( \sum_{k = 0}^n a_k \right) x^n. $$

That is, multiplication by $(1 - x)^{-1}$ gives you the partial sums of a series. The partial sums of

$$ \frac{1}{1 - x^3} = 1 + x^3 + x^6 + x^9 + \cdots $$

are given by

$$ (1 + x + x^2) + 2(x^3 + x^4 + x^5) + 3(x^6 + x^7 + x^8) + 4\cdots. $$

Which can be described as

$$ [x^n] \frac{1}{(1 - x)^2(1 + x + x^2)} = \left\lfloor \frac{n}{3} \right\rfloor + 1. $$

---

The second way, which is what you are trying to do, uses the fundamental property of rational generating functions (c.f. Stanley EC1 Theorem 4.1.1) which implies that

$$ [x^n] \frac{1}{(1 - x)^2(1 + x + x^2)} = (A + Bn)1^n + C\left( \cos \frac{\pi}{3} + i \sin \frac{\pi}{3} \right)^n + D \left( \cos \frac{\pi}{3} - i \sin \frac{\pi}{3} \right)^n $$

Which if you look at the first 4 coefficients give you enough information to determine (here it's helpful to use a computer rather than do this by hand)

$$ [x^n] \frac{1}{(1 - x)^2(1 + x + x^2)} = \frac{2}{3} + \frac{1}{3}n + \frac{1}{3} \cos\left(\frac{2 n \pi}{3}\right) + \frac{1}{3 \sqrt 3} \sin\left(\frac{2 n \pi}{3}\right). $$

Then, using the periodicity of sine and cosine, we see that when $n \equiv 0 \pmod 3$ we have

$$ \frac{2}{3} + \frac{1}{3}n + \frac{1}{3} = \frac{n}{3} + 1. $$

When $n \equiv 1 \pmod 3$ we have

$$ \frac{2}{3} + \frac{1}{3}n - \frac{1}{6} + \frac{1}{6} = \frac{n - 1}{3} + 1. $$

And finally, when $n \equiv 2 \pmod 3$ we have

$$ \frac{2}{3} + \frac{1}{3}n - \frac{1}{6} - \frac{1}{6} = \frac{n - 2}{3} + 1. $$

This three cases can be described together as

$$ \left\lfloor \frac{n}{3} \right\rfloor + 1. $$

Answer 2

Hint: We use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ in a series $A(x)=\sum_{k=0}^\infty a_kx^k$ and write \begin{align*} [x^n]A(x)=[x^n]\sum_{k=0}^\infty a_kx^k=a_n \end{align*}

In the current situation we consider \begin{align*} [x^n]\frac{1}{(1-x)^3(1-x)}\tag{1} \end{align*}

An expansion of the other representation $\frac{1}{(1-x)^2(1+x+x^2)}$ is possible, but less convenient. In both cases we have two series to expand and the series expansion in (1) is somewhat simpler.

We obtain \begin{align*} \color{blue}{[x^n]\frac{1}{(1-x)^3(1-x)}}&=[x^n]\left(\sum_{k=0}^\infty x^k\sum_{j=0}^\infty x^{3j}\right)\tag{2}\\ &=\sum_{k=0}^n [x^{n-k}]\left(\sum_{j=0}^\infty x^{3j}\right)\tag{3}\\ &=\sum_{k=0}^n [x^k]\left(\sum_{j=0}^\infty x^{3j}\right)\tag{4}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{3}\right\rfloor} 1\tag{5}\\ &\color{blue}{=\left\lfloor\frac{n}{3}\right\rfloor+1} \end{align*}

Comment:

• In (2) we expand both series using the binomial series expansion.

• In (3) we use the linearity of the coefficient of operator and apply the rule $[x^{p-q}]A(x)=[x^p]x^qA(x)$. We also set the upper bound of the left-hand sum to $n$ since other indices do not contribute to the coefficient of $x^n$.

• In (4) we change the order of summation of the left-hand sum by setting $k\rightarrow n-k$.

• In (5) we select the coefficient of $x^k$ by noting that only multiples of three provide a non-zero contribution.