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

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?

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$$.

\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$$.

• Thank you @Joshua P. Swanson for your response! I'm still quite confused about how the coefficient of x^n is 1 + (n/r) because say if the r-value is 5 and I'm finding the coefficient of an n-degree is not a multiple of 5 (eg. n = 14), wouldn't the coefficient not tabulate? I would get a fraction although the answer is supposed to be 3. I can only see how the coefficient of x^n being 1 + (n/r) works when the n value is a multiple of r.
– boop
Jul 3 '21 at 7:10
• You're ignoring the floor symbols. They tell you to just ignore the fractional part and truncate at the nearest lower integer. Jul 3 '21 at 17:22