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.


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.

  • $\begingroup$ You start by finding the generating function. Did you get that far? Where are you stuck? $\endgroup$ – Trevor Gunn Oct 21 '17 at 1:50
  • $\begingroup$ 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+...)$. $\endgroup$ – jallen3095 Oct 21 '17 at 3:40
  • $\begingroup$ 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\}$. $\endgroup$ – N. F. Taussig Oct 21 '17 at 19:49
  • $\begingroup$ That's the same number of solutions I was thinking also. For some reason I cannot get my convolution to produce the same value. $\endgroup$ – jallen3095 Oct 21 '17 at 20:41
  • $\begingroup$ Well, for one thing, your formula for $b_n$ is incorrect. Can you see why? $\endgroup$ – Qudit Oct 22 '17 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.