Generating functions for the solutions to $3x_1 + x_2 = n$ 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.
 A: 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.
A: 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. $$
