How do you prove the Cauchy product (multiplication) of two infinite power series (generating functions) which have different exponents/indices?
Solution 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$.