Determine generating function for a sequence

193 Views Asked by At

Let $b_n$ be the number of non-negative integral solutions of $2x_1+3x_2+5x_3=n.$

We need to determine the generating function of {$b_n$}.

My attempt:

$x_1=0,2,4,6,8,...$

$x_2=0,3,6,9,12,...$

$x_3=0,5,10,15,...$

Then,$$\sum_{k\ge0} b_kx^k = (x^0+x^2+x^4+...)(x^0+x^3+x^6+...)(x^0+x^5+x^{10}+...)$$ $$=(\frac{1}{1-x^2})(\frac{1}{1-x^3})(\frac{1}{1-x^5})$$

Am I on the right track? If this is correct, what steps would I need to make in order to determine the generating function?

1

There are 1 best solutions below

0
On BEST ANSWER

What you really mean is not that $x_1$ is an even natural number, but rather that $2x_1$ is. Similarly, it’s $3x_2$ that is a non-negative multiple of $3$, not $x_2$ itself, and $5x_3$ that is a non-negative multiple of $5$. That said, however, the rest is fine as far as it goes: the number of solutions to $$2x_1+3x_2+5x_3=n$$ in non-negative integers is indeed the coefficient of $x^n$ in

$$\left(\frac1{1-x^2}\right)\left(\frac1{1-x^3}\right)\left(\frac1{1-x^5}\right)=\frac1{(1-x^2)(1-x^3)(1-x^5)}\;,$$

and this function of $x$ is your generating function. You’re done at this point, unless you are also required to get a closed form for $b_n$. That, however, would be very difficult; this sequence of numbers is OEIS A025795, and the only closed forms shown are rather complicated.