How to expand $\frac1{(1-x)(1-x^2)(1-x^5)}$

Question

How do I expand

$$\frac1{(1-x)(1-x^2)(1-x^5)}$$

I need to find the coefficent of $x^9$, but I also want to be able to derive the general form. The only method I could thing of was to expand the $3$ individual denominators into an infinite GP and then count the number of ways I can get $x^9$, but not only is that time consuming, I cannot get a general formula for it. Can you please help me?

Answer 1

We expand $\frac{1}{(1-x)(1-x^2)(1-x^5)}$ without using complex roots. This is somewhat cumbersome, but nevertheless feasible. We start with a partial fraction decomposition of $\frac{1}{(1-x)(1-x^2)}$ which has only real valued roots in the denominator.

We obtain \begin{align*} \color{blue}{\frac{1}{(1-x)(1-x^2)}}&=\frac{1}{(1-x)^2(1+x)}\\ &=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{1+x}\tag{1}\\ &=\frac{1}{4(1-x)}+\frac{1}{2(1-x)^2}+\frac{1}{4(1+x)}\tag{2}\\ &=\frac{1}{4}\sum_{j=0}^\infty x^j+\frac{1}{2}\sum_{j=0}^\infty (j+1)x^j+\frac{1}{4}\sum_{j=0}^\infty (-1)^jx^j\tag{3}\\ &\,\,\color{blue}{=\frac{1}{4}\sum_{j=0}^\infty\left(2j+3+(-1)^j\right)x^j}\tag{4} \end{align*}

Comment:

• In (1) we do the partial fraction decomposition using an Ansatz with unknown constants $A,B$ and $C$.

• In (2) we calculate the constants by multiplying out and comparing coefficients of equal powers of $x$ (or we ask Wolfram Alpha for support).

• In (3) we expand the first and last expression using the geometric series expansion and use for the middle term the binomial series expansion $$\frac{1}{(1-x)^2}=\sum_{j=0}^\infty\binom{-2}{j}(-x)^j=\sum_{j=0}^\infty \binom{j+1}{j}x^j=\sum_{j=0}^\infty (j+1)x^j$$

• In (4) we collect the terms with equal powers in $x$.

We are now ready for multiplying and expanding with $\frac{1}{1-x^5}$. We obtain from (4) \begin{align*} &\color{blue}{\frac{1}{(1-x)(1-x^2)(1-x^5)}}\\ &\quad\qquad=\frac{1}{4}\sum_{j=0}^{\infty}\left(2j+3+(-1)^j\right)x^j\sum_{k=0}^\infty x^{5k}\\ &\quad\qquad=\frac{1}{4}\sum_{n=0}^\infty \sum_{{j+5k=n}\atop{j,k\geq 0}}(2j+3+(-1)^j)\,x^n\tag{5}\\ &\quad\qquad=\frac{1}{4}\sum_{n=0}^\infty\left(\sum_{j=0}^n\left(10j+3+(-1)^j\right)x^{5n}\right.\\ &\quad\qquad\qquad\qquad\quad+\sum_{j=0}^\infty\left(10j+5+(-1)^{j+1}\right)x^{5n+1}\\ &\quad\qquad\qquad\qquad\quad+\sum_{j=0}^\infty\left(10j+7+(-1)^{j}\right)x^{5n+2}\tag{6}\\ &\quad\qquad\qquad\qquad\quad+\sum_{j=0}^\infty\left(10j+9+(-1)^{j+1}\right)x^{5n+3}\\ &\quad\qquad\qquad\qquad\quad+\sum_{j=0}^\infty\left(10j+11+(-1)^{j}\right)x^{5n+4}\Bigg)\\ &\quad\qquad=\frac{1}{4}\sum_{n=0}^\infty\sum_{l=0}^4\sum_{j=0}^n\left(10j+3+2l+(-1)^{j+l}\right)x^{5n+l}\tag{7}\\ &\quad\qquad=\frac{1}{4}\sum_{n=0}^\infty\sum_{l=0}^4\left(10\frac{n(n+1)}{2}+(3+2l)(n+1)+(-1)^{l}\frac{1+(-1)^n}{2}\right)x^{5n+l}\tag{8}\\ &\quad\qquad\,\,\color{blue}{=\frac{1}{4}\sum_{n=0}^\infty\sum_{l=0}^4\left((n+1)(5n+3+2l)+(-1)^{l}\frac{1+(-1)^n}{2}\right)x^{5n+l}}\tag{9}\\ \end{align*}

and we have found a (let's say) nice series expansion. We can now harvest and calculate the coefficient $[x^9]$ from $\frac{1}{(1-x)(1-x^2)(1-x^5)}$ by setting $n=1$ and $l=4$ in (9) to get

\begin{align*} \color{blue}{[x^9]}&\color{blue}{\frac{1}{(1-x)(1-x^2)(1-x^5)}}\\ &=[x^9]\frac{1}{4}\sum_{n=0}^\infty\sum_{l=0}^4\left((n+1)(5n+3+2l)+(-1)^{l}\frac{1+(-1)^n}{2}\right)x^{5n+l}\\ &=\frac{1}{4}(1+1)(5+3+8)+(-1)^4\frac{1+(-1)^1}{2}\\ &\,\,\color{blue}{=8} \end{align*}

Comment:

• In (5) we multiply the series using the Cauchy product.

• In (6) we rearrange the series according to residue classes $\mathrm{mod} \ 5$. The first series with $x^{5n}$ corresponds to $j$-values being multiples of $5$: $j=0,5,10,\ldots$. The next series with $x^{5n+1}$ corresponds to $j=1,6,11,\ldots$, etc.

• In (7) we use a slightly more compact notation and write the $5$ parts by summing up over $l=0,1,2,3,4$.

• In (8) we do some simplifications using the formulas: $\sum_{j=0}^n c=(n+1)c$ and $\sum_{j=0}^n j=\frac{n(n+1)}{2}$. We also see that summing up $(-1)^j$ gives the sequence $1,0,1,0,1,\ldots$.

• In (9) we finally collect corresponding terms.

Answer 2

If you settle down and actually do it, it is not that time consuming.
So you have $\frac1{(1-x)(1-x^2)(1-x^5)}$ here. Expanding each factor gives: $$ \frac1{1-x^n}=\sum_{i=0}^\infty x^{in}.$$ In order to find the ways you can get $x^8$, just count how many ways you can get $8$ by combining (adding, because exponents add when multiplied, i.e. $x^2x^5x^1=x^{2+5+1}=x^8$.) $1,2$ and $5$. This follows directly from the expansion process. You can get the following: $$ \begin{align} 8&=1+1+1+1+1+1+1+1\\ &=1+1+1+1+1+1+2\\ &=1+1+1+1+2+2\\ &=1+1+2+2+2\\ &=2+2+2+2\\ &=1+1+1+5\\ &=1+2+5. \end{align} $$

Hopefully, I haven't missed any combination, and in that case, there will be 7 ways. So the coefficient of $x^8$ is $9$.

In fact, this formula is quite important when studying partition numbers, that is, how many different ways there are to break a natural number into sums of positive integers. The number of ways to partition $n$ would then be the coefficient of $x^n$ in the expansion of $$ \prod_{m=1}^\infty \frac1{1-x^m}, $$ whose proof is left as an exercise for you.

Answer 3

In $$(1+x+x^2+x^3+\cdots)(1+x^2+x^4+x^6+\cdots)(1+x^5+x^{10}+x^{15}+\cdots)$$ the degree $9$ is obtained when

$$p+2q+5r=9$$

and you need to find the number of solutions. We have

$$(0,2,1),(1,4,0),(2,1,1),(3,3,0),(4,0,1),(5,2,0),(7,1,0),(9,0,0)$$ hence the coefficient is $8$.

---

Let $f(n)$ denote the number of admissible solutions of

$$a+2b=n.$$

It is not a big deal to establish

$$f(n)=\left\lfloor\frac n2\right\rfloor+1.$$

Now let $g(n)$ denote the number of solutions of

$$a+2b+5c=n.$$

We have

$$g(n)=\sum_{c=0}^{\lfloor\frac n5\rfloor}f(n-5c)=\sum_{c=0}^{\lfloor\frac n5\rfloor}\left(\left\lfloor\frac{n-5c}2\right\rfloor+1\right).$$

With $q:=\lfloor\frac n5\rfloor+1$, this sum is

$$\frac{nq}2-\frac{5(q-1)q}4+q-\left\lfloor\frac q2\right\rfloor.$$

This result is obtained by temporarily ignoring the floor, summing, then correcting as half of the terms were exaggerated by $\frac12$.

(Caution: this formula might be in error by $\frac12$ depending on the parity of $n$.)