-1

Given the generating function below, I was struggling trying to come up with a way to get a closed form for the coefficients. $$F(X) = \frac{x^8(x+x^2+x^3)}{(1-x^5)(1-x^2)(1-x)}$$

The question I got this from asked for the closed form of $x_1+5x_2+2x_3+x_4=n$ if $x_4\le3$ and $x_i\ge1$.

I started by trying out partial fraction decomposition, but I'm not sure how to approach it, and there aren't any other avenues I can think of right now. Any advice would be much appreciated!

Parcly Taxel
  • 103,344
Quincy Adams
  • 11
  • 1
    Partial fraction decomposition will work but it's slightly tricky because $1$ is a root of multiplicity $3$ in the denominator. Are you familiar with what partial fraction decomposition looks like when there are multiplicities? – Qiaochu Yuan Oct 10 '22 at 01:22
  • I am a little bit familiar, but only with multiplicities of x^2 on the bottom. That's part of what confused me here. The question I got this from, for context if needed, asked for closed form of x1+x2+x3+x4=n if x2 was a multiple of 5, x3 was a multiple of 2, x4 was at most 3, and all of them were at least 1 – Quincy Adams Oct 10 '22 at 01:55
  • Partial fraction decomposition in this case says that one of the terms has the form $\frac{f(x)}{(1 - x)^3}$ where $f(x)$ is quadratic; alternatively you can use three terms of the form $\frac{a}{(1 - x)^3}, \frac{b}{(1 - x)^2}, \frac{c}{1 - x}$. Either way there are three coefficients to solve for. – Qiaochu Yuan Oct 10 '22 at 02:14
  • I bet that the $x^8$ is a red herring – Claude Leibovici Oct 10 '22 at 04:06
  • If you know complex analysis, the techniques here might work, although this will require looking at 6 different points, including the 5th roots of unity, to make it work, and it might not be worth it in the end. – Aaron Oct 10 '22 at 07:22
  • Why are did you hide the major part of the problem ? – Claude Leibovici Oct 10 '22 at 09:26

2 Answers2

1

This is more than a hint but less than a solution, though it should be enough to guide you towards one with a bit of work.

Here is a general form of partial fractions that you can use. Suppose that we have a rational function $$R(x)=\frac{f(x)}{g_1(x)g_2(x)\ldots g_n(x)}.$$

Further, suppose that the total degree on top is strictly smaller than the total degree on the bottom, and that all the $g_i(x)$ are relatively prime, that is, they have no factors in common. Then we can find $f_1(x), \ldots, f_n(x)$ with $\deg f_i(x)<\deg g_i(x)$ such that

$$R(x)=\sum_i \frac{f_i(x)}{g_i(x)}.$$

In your particular case, the factors in the bottom all share a factor of $(1-x)$, and so you will have to factor that out and group them all together. Additionally, since the goal is to find a power series, and multiplying a power series by $x^k$ is easy, you might as well factor out $x^9$ from the numerator. This reduces the problem to expressing

$$ \frac{1+x+x^2}{(1-x^5)(1-x^2)(1-x)} = \frac{f_1(x)}{1+x+x^2+x^3+x^4} + \frac{f_2(x)}{1+x}+\frac{f_3(x)}{(1-x)^3}$$ where $\deg f_1(x)\leq 3, \deg f_2(x)=0, \deg f_3(x)\leq 2$.

Multiplying through to clear denominators, this becomes

$$1+x+x^2=f_1(x)(1-x^2)(1-x)^2 + f_2(x)(1-x^5)(1-x)^2 + f_3(x)(1+x+x^2+x^3+x^4)(1+x).$$

Unfortunately, from this point, there is messy algebra to do, plugging in generic polynomials with undetermined coefficients for the $f_i(x)$ and solving. There are a few little tricks you can use to aid your work, but it's going to be rough going in any case, but it is doable. As a hint for this part, I suggest using the fact that if $h(x)=(1-x)^3g(x)$, then $h(1)=h'(1)=h''(1)=0$ in order to find $f_3(x)$ first, and plug in $x=-1$ to find $f_2(x)$. This will leave only $f_1(x)$ unknown, and at this point you can either expand out and compare coefficients or plug in at 4 other random points (such as $0$, $\pm 2$, $3$) to get a system of linear equations to solve for the coefficients. But there are many ways to approach this, so don't feel constrained.

In the final step, when you're looking to get an explicit form of the power series, one nice trick will be to write $$ \frac{f_1(x)}{1+x+x^2+x^3+x^4}=\frac{(1-x)f_1(x)}{1-x^5} $$ and use the fact that $\frac{1}{1-x^5}=\sum_{n=0}^{\infty}x^{5n}.$

Good luck!

Aaron
  • 24,207
  • Taking a look at this approach it definitely seems doable, albeit the algebra does seem like its going to be a massive pain ;). I'll try splitting it up with the factoring you mentioned and powering through for the partial fraction, and it should give me an answer – Quincy Adams Oct 10 '22 at 15:05
  • Wolfram Alpha (effectively) says the result is $x^9$ times $$-\frac{1}{5}\frac{1-2x^2+x^4}{1-x^5}+\frac{1/8}{1+x}+\frac{13/40}{1-x}+\frac{9/20}{(1-x)^2}+\frac{3/10}{(1-x)^3}.$$ – anon Oct 10 '22 at 15:42
0

Hint

If you start with the long division (forget the $x^8$ for the time being), you will see that the result is in fact $$F(x)=x^9 \sum_{n=0}^\infty a_n\,x^n$$ So, write $$\frac{x^8(x+x^2+x^3)}{(1-x^5)(1-x^2)(1-x)}=x^9 \sum_{n=0}^\infty a_n\,x^n$$ that is to say $$1+x+x^2=(1-x^5)(1-x^2)(1-x)\sum_{n=0}^\infty a_n\,x^n$$ Proceed as usual to find the recurrence relation for the $a_n$'s.

Claude Leibovici
  • 260,315
  • 1
    The goal is to find a closed form formula, and finding a recurrence relation seems antithetical to this. In fact, I suspect that a recurrence relation was used to find the generating function, so this is likely undoing a step that was already done. – Aaron Oct 10 '22 at 05:21
  • @Aaron. For this problem, I do not think that we can have anything else than a reccurence relation. It took me 15 minutes with pen and paper to et it. It is not the most simple. – Claude Leibovici Oct 10 '22 at 06:19
  • 1
    From the partial fraction decomposition I work towards in my "answer", an explicit formula is definitely possible, although it may have to have a term that depends on what $n$ is mod 5. It will be messy, but it exists. – Aaron Oct 10 '22 at 07:10