How do you prove the Cauchy product (multiplication) of two infinite power series (generating functions) which have different exponents/indices?

Question

I'm trying to multiply 2 generating functions ( (1/(1-x) ) and ( 1/(1-x^5) ) which have different denominations so that I can find the coefficient. When browsing math.stackexchange I found the equation:

\begin{align*} \frac{1}{1-x}\cdot\frac{1}{1-x^r}=\sum_{n\ge 0} \left(1+\left\lfloor\frac{n}{r}\right\rfloor\right)x^n \end{align*}

Could someone go through all of the steps of the equation and explain how and why the product of these two power series are equivalent to the summation shown on the right?

Answer 1

We obtain \begin{align*} \color{blue}{\frac{1}{1-x}\cdot\frac{1}{1-x^r}} &=\sum_{k=0}^\infty x^k\sum_{l=0}^\infty \left(x^r\right)^l\tag{1}\\ &=\sum_{k=0}^\infty x^k\sum_{l=0}^\infty x^{rl}\\ &=\sum_{n=0}^\infty \left(\sum_{{k+rl=n}\atop {k,l\geq 0}} 1\right) x^n\tag{2}\\ &=\sum_{n=0}^\infty \left(\sum_{k=0}^{\left\lfloor\frac{n}{r}\right\rfloor} 1\right)x^n\tag{3}\\ &\,\,\color{blue}{=\sum_{n=0}^\infty \left(1+\left\lfloor\frac{n}{r}\right\rfloor\right)x^n}\tag{4} \end{align*} and the claim follows.

Comment:

• In (1) we apply the geometric series expansion twice.

• In (2) we multiply out using the Cauchy-product.

• In (3) we eliminate the index $l$. Due to the factor $r$ and the relation $k=n-r\cdot l$ the upper limit of $k$ is set to $\left\lfloor\frac{n}{r}\right\rfloor$.

• In (4) we simplify the inner sum noting that since we start with $k=0$ we have the additional term $1$.

Answer 2

\begin{align*} \frac{1}{1-x} \frac{1}{1-x^r} &= (1+x+x^2+\cdots)(1+x^r+x^{2r}+\cdots) \\ &= 1+x+x^2+\cdots \\ &+ x^r+x^{r+1}+x^{r+2}+\cdots \\ &+ x^{2r} + x^{2r+1} + x^{2r+2} + \cdots \\ &+ \cdots \end{align*} Every exponent from $x^0, \ldots, x^{r-1}$ is included once, every exponent from $x^r, \ldots, x^{2r-1}$ is included twice, etc. So the coefficient of $x^n$ is $1 + \lfloor n/r\rfloor$.