# Number of Solutions Using Generating Functions

I am struggling with the following problem and I was hoping somebody could help me.

Solve by applying the convolution formula for generating functions: How many nonnegative integer solutions are there for $x_1 + 3x_2 = 100$?

I've been getting really high numbers in my attempts so far and there's no way that they are correct. If someone can help me get started that would be appreciated.

Thanks!

EDIT: Here is my work so far which is giving me the answer 176,851 solutions which I'm sure is wrong.

$G(x)=(1+x+x^2+x^3+...)(1+x^3+x^6+x^9+...)$ --> $G(x)=(1/(1-x))(1/(1-x^3))$ $a_n=1$ and $b_n=C((n+2), 2)$

Then I'm finding the coefficient of $x^{100}$ from the convolution formula.

• You start by finding the generating function. Did you get that far? Where are you stuck? – Trevor Gunn Oct 21 '17 at 1:50
• Yes, I think I have the generating function figured out. I'm using $G(x) = (1+x^2+x^3+x^4...)(1+x^3+x^6+x^9+...)$. – jallen3095 Oct 21 '17 at 3:40
• By inspection, there are $34$ solutions. Since $x_1, x_2$ must be nonnegative, $x_1 = 100 - 3x_2 \implies x_2 \in \{0, 1, 2, 3, \ldots, 33\}$. – N. F. Taussig Oct 21 '17 at 19:49
• That's the same number of solutions I was thinking also. For some reason I cannot get my convolution to produce the same value. – jallen3095 Oct 21 '17 at 20:41
• Well, for one thing, your formula for $b_n$ is incorrect. Can you see why? – Qudit Oct 22 '17 at 19:13